コンテンツにスキップ

DOJ Beginner Contest 9 G - Pi Problem

サイト
DOJ
コンテスト
DOJ Beginner Contest 9
問題
G - Pi Problem

正の整数 a,ba, b に対して、aa の十進表記を bb 回つなげた整数を rep(a,b)\mathrm{rep}(a, b) とします。たとえば rep(31,4)=31313131\mathrm{rep}(31, 4) = 31313131 です。

長さ NN の正整数列 AA が与えられるので、

∏1≤i<j≤Nrep(Ai,Aj)\prod_{1 \le i < j \le N} \mathrm{rep}(A_i, A_j)

を 998244353998244353 で割った余りを求める問題です。Ai≤109A_i \le 10^9 で、NN の総和は 2×1052 \times 10^5 以下です。

aa が kk 桁のとき、aa を bb 回つなげることは、aa に 1+10k+102k+⋯+10(b−1)k1 + 10^k + 10^{2k} + \dots + 10^{(b-1)k} を掛けることと同じです。等比数列の和を使うと

rep(a,b)=a⋅10kb−110k−1\mathrm{rep}(a, b) = a \cdot \frac{10^{kb} - 1}{10^k - 1}

です。以下、kk 桁の数を bb 回つなげたときに掛かる部分を fk(b)=10kb−110k−1f_k(b) = \dfrac{10^{kb} - 1}{10^k - 1} と書きます。

AiA_i の桁数を kik_i とすると、求める積は

∏i<jAi⋅fki(Aj)=(∏i<jAi)(∏i<jfki(Aj))\prod_{i < j} A_i \cdot f_{k_i}(A_j) = \left( \prod_{i < j} A_i \right) \left( \prod_{i < j} f_{k_i}(A_j) \right)

と分けられます。

前半では、AiA_i は自分より後ろの jj の個数だけ掛かるので、∏iAiN−i\prod_i A_i^{N - i} です。

後半は、jj ごとにまとめます。Ai≤109A_i \le 10^9 なので桁数 kk は 11 から 1010 までしかありません。i<ji < j で桁数が kk のものの個数を cj,kc_{j,k} とすると、後半は

∏j∏k=110fk(Aj)cj,k\prod_j \prod_{k=1}^{10} f_k(A_j)^{c_{j,k}}

です。cj,kc_{j,k} は桁数ごとの個数を数えながら jj を動かせば求まります。fk(Aj)f_k(A_j) は 11 つの jj につき 1010 通りしかないので、全体で O(10Nlog⁡A)O(10 N \log A) 回程度の計算で済みます。

fk(b)f_k(b) を 998244353998244353 で割った余り

Section titled “fk(b)f_k(b)fk​(b) を 998244353998244353998244353 で割った余り”

fk(b)f_k(b) は割り算を含みます。10k−110^k - 1 の逆元を使ってもよいのですが、解答コードでは逆元を使わずに計算しています。

M=998244353M = 998244353、d=10k−1d = 10^k - 1、X=10kb−1X = 10^{kb} - 1 とします。XX は dd で割り切れます。XX を dMdM で割った余りを rr とすると、X=q⋅dM+rX = q \cdot dM + r と書けて、rr も dd で割り切れます。両辺を dd で割ると

Xd=qM+rd\frac{X}{d} = qM + \frac{r}{d}

なので、Xd\dfrac{X}{d} を MM で割った余りは rd\dfrac{r}{d} を MM で割った余りと同じです。つまり、10kb10^{kb} を dMdM を法として計算し、11 を引いてから dd で割れば、fk(b)f_k(b) を MM で割った余りが求まります。

Python
MOD = 998244353
for _ in range(int(input())):
N = int(input())
A = list(map(int, input().split()))
ans = 1
d = [0] * 11
for i in range(N):
ans *= pow(A[i], N - i - 1, MOD)
ans %= MOD
d[len(str(A[i]))] += 1
for i in reversed(range(N)):
d[len(str(A[i]))] -= 1
for j in range(1, 11):
if d[j] == 0:
continue
b = 10**j - 1
x = pow(10, j * A[i], b * MOD)
x -= 1
x %= b * MOD
assert x % b == 0
x //= b
ans *= pow(x, d[j], MOD)
ans %= MOD
print(ans)

最初のループで前半の積を計算し、桁数ごとの個数 d を数えます。2 つ目のループでは後ろから見ていき、d から自分を引くことで、d[j] が「自分より前にある jj 桁の数の個数」になるようにしています。