314 Triplet Problem

2 secs 1024 MB
loop0919's icon loop0919
Tweet
問題
提出
テストケース
解説

解説

[0] 準備

以下を前提に解説します。

  • 正整数 nn に対し d(n)d(n) を、 nn を十進表記したときの桁数と定義します。

  • ii についての任意の式 F(i)F(i) について、 l>rl > r ならば ∑i=lrF(i)=0\displaystyle\sum_{i = l}^r F(i) = 0 であるとします。

  • f(a,b,c)=a⋅10d(b)+d(c)+b⋅10d(c)+cf(a, b, c) = a \cdot 10^{d(b) + d(c)} + b \cdot 10^{d(c)} + c と表すことができます。

[1] 各 cc ごとの寄与

ここで a+b=ca + b = c の条件から、 cc を固定したときの寄与 G(c)G(c) は

G(c)=∑b=1c−1f(c−b,b,c)=∑b=1c−1((c−b)⋅10d(b)+d(c)+b⋅10d(c)+c)=10d(c)∑b=1c−1(c−b)10d(b)+10d(c)∑b=1c−1b+c∑b=1c−11=10d(c)∑b=1c−1(c−b)10d(b)+(10d(c)+2)c(c−1)2\begin{aligned} G(c) &= \sum_{b = 1}^{c - 1}f(c - b, b, c) \\ &= \sum_{b = 1}^{c - 1} \Big((c - b) \cdot 10^{d(b) + d(c)} + b \cdot 10^{d(c)} + c\Big) \\ &= 10^{d(c)}\sum_{b = 1}^{c - 1} (c - b) 10^{d(b)} + 10^{d(c)} \sum_{b = 1}^{c - 1}b + c\sum_{b = 1}^{c - 1}1 \\ &= 10^{d(c)}\sum_{b = 1}^{c - 1} (c - b) 10^{d(b)} + (10^{d(c)} + 2) \frac{c(c - 1)}{2} \end{aligned}

と計算できます。

残った ∑b=1c−1(c−b)10d(b)\displaystyle \sum_{b = 1}^{c - 1} (c - b) 10^{d(b)} について、

  • d(c)d(c) 桁未満の bb はすべて含まれる
  • d(c)d(c) 桁の bb は 10d(c)−110^{d(c) - 1} から c−1c - 1 まで含まれる

ことを考慮すると、bb が d(c)d(c) 桁未満の場合とちょうど d(c)d(c) 桁の場合に分ける発想が出ます。

そこで、前計算として

P[x]:=∑i=110x−110d(i),Q[x]:=∑i=110x−1i⋅10d(i)P[x] := \sum_{i = 1}^{10^x - 1} 10^{d(i)}, \enspace Q[x] := \sum_{i = 1}^{10^x - 1} i \cdot 10^{d(i)}

を定義すると、以下のように式変形できます。

∑b=1c−1(c−b)10d(b)=cP[d(c)−1]−Q[d(c)−1]+10d(c)∑b=10d(c)−1c−1(c−b)=cP[d(c)−1]−Q[d(c)−1]+10d(c)⋅(c−10d(c)−1)(c−10d(c)−1+1)2\begin{aligned} \displaystyle \sum_{b = 1}^{c - 1} (c - b) 10^{d(b)} &= c P[d(c) - 1] - Q[d(c) - 1] + 10^{d(c)} \sum_{b = 10^{d(c) - 1}}^{c - 1} (c - b) \\ &= c P[d(c) - 1] - Q[d(c) - 1] + 10^{d(c)} \cdot \frac{(c - 10^{d(c) - 1})(c - 10^{d(c) - 1} + 1)}{2} \end{aligned}

これにより、固定したある cc に対する寄与 G(c)G(c) を、適切な前計算のもと求めることができます。

P,QP, Q の前計算について、xx 桁の整数は 10x−110^{x - 1} 以上 10x−110^x - 1 以下であるため、

P[x]=P[x−1]+10x⋅9⋅10x−1Q[x]=Q[x−1]+10x+∑i=10x−110x−1iP[x] = P[x - 1] + 10^{x} \cdot 9 \cdot 10^{x - 1}\\ Q[x] = Q[x - 1] + 10^{x} + \sum_{i = 10^{x - 1}}^{10^x - 1} i

と計算できます。

[2] 各寄与を桁ごとに計算

cc が qq 桁である範囲は Lq=10q−1L_q = 10^{q - 1} 以上 Rq=min⁡(N,10q−1)R_q = \min(N, 10^q - 1) 以下です。

計算のために以下の式を導入します。

S1(n)=∑i=1ni=n(n+1)2S2(n)=∑i=1ni(i−1)2=n(n+1)(n−1)6S3(n)=∑i=1ni(i+1)2=n(n+1)(n+2)6S_1(n) = \sum_{i = 1}^n i = \frac{n(n + 1)}{2} \\ S_2(n) = \sum_{i = 1}^n \frac{i(i - 1)}{2} = \frac{n(n + 1)(n - 1)}{6} \\ S_3(n) = \sum_{i = 1}^n \frac{i(i + 1)}{2} = \frac{n(n + 1)(n + 2)}{6}

そうすると、 cc の桁数が qq 桁であるようなものの寄与の総和 Block(q)\mathrm{Block}(q) は

Block(q)=10q(P[q−1]∑c=LqRq−Q[q−1](R−L+1)+10q∑c=LqRq(c−10q−1)(c−10q−1+1)2)+(10q+2)∑c=LqRqc(c−1)2\mathrm{Block}(q) = 10^q \Big(P[q - 1] \sum_{c = L_q}^{R_q} - Q[q - 1](R - L + 1) + 10^q \sum_{c = L_q}^{R_q} \frac{(c - 10^{q - 1})(c - 10^{q - 1} + 1)}{2}\Big) + (10^q + 2)\sum_{c = L_q}^{R_q} \frac{c(c-1)}{2}

となり、S1,S2,S3S_1, S_2, S_3 を用いて

∑c=LqRqc=S1(Rq)−S1(Lq−1)∑c=LqRqc(c−1)2=S2(Rq)−S2(Lq−1)∑c=LqRq(c−10q−1)(c−10q−1+1)2=S3(Rq−10q−1)−S3(Lq−10q−1−1)\sum_{c=L_q}^{R_q} c = S_1(R_q) - S_1(L_q - 1)\\ \sum_{c = L_q}^{R_q} \frac{c(c-1)}{2} = S_2(R_q) - S_2(L_q - 1)\\ \sum_{c = L_q}^{R_q} \frac{(c - 10^{q - 1})(c - 10^{q - 1} + 1)}{2} = S_3(R_q - 10^{q - 1}) - S_3(L_q - 10^{q - 1} - 1)

と計算することができました。
q=1,2,3,⋯q = 1, 2, 3, \cdots に対してこの値を求め、それらの総和を 998244353998244353 で割った余りが答えとなります。

これにより、本問題を解くことができました。計算量は O(log⁡N)O(\log N) です。

ここで、計算中に発生する除算は、mod 998244353\mathrm{mod}~ 998244353 上の逆元を用いて計算する必要があることに注意してください。