正の整数 a,b に対して、a の十進表記を b 回つなげた整数を rep(a,b) とします。たとえば rep(31,4)=31313131 です。
長さ N の正整数列 A が与えられるので、
1≤i<j≤N∏rep(Ai,Aj)
を 998244353 で割った余りを求める問題です。Ai≤109 で、N の総和は 2×105 以下です。
a が k 桁のとき、a を b 回つなげることは、a に 1+10k+102k+⋯+10(b−1)k を掛けることと同じです。等比数列の和を使うと
rep(a,b)=a⋅10k−110kb−1
です。以下、k 桁の数を b 回つなげたときに掛かる部分を fk(b)=10k−110kb−1 と書きます。
Ai の桁数を ki とすると、求める積は
i<j∏Ai⋅fki(Aj)=(i<j∏Ai)(i<j∏fki(Aj))
と分けられます。
前半では、Ai は自分より後ろの j の個数だけ掛かるので、∏iAiN−i です。
後半は、j ごとにまとめます。Ai≤109 なので桁数 k は 1 から 10 までしかありません。i<j で桁数が k のものの個数を cj,k とすると、後半は
j∏k=1∏10fk(Aj)cj,k
です。cj,k は桁数ごとの個数を数えながら j を動かせば求まります。fk(Aj) は 1 つの j につき 10 通りしかないので、全体で O(10NlogA) 回程度の計算で済みます。
fk(b) は割り算を含みます。10k−1 の逆元を使ってもよいのですが、解答コードでは逆元を使わずに計算しています。
M=998244353、d=10k−1、X=10kb−1 とします。X は d で割り切れます。X を dM で割った余りを r とすると、X=q⋅dM+r と書けて、r も d で割り切れます。両辺を d で割ると
dX=qM+dr
なので、dX を M で割った余りは dr を M で割った余りと同じです。つまり、10kb を dM を法として計算し、1 を引いてから d で割れば、fk(b) を M で割った余りが求まります。
Python
for _ in range(int(input())):
A = list(map(int, input().split()))
ans *= pow(A[i], N - i - 1, MOD)
for i in reversed(range(N)):
x = pow(10, j * A[i], b * MOD)
最初のループで前半の積を計算し、桁数ごとの個数 d を数えます。2 つ目のループでは後ろから見ていき、d から自分を引くことで、d[j] が「自分より前にある j 桁の数の個数」になるようにしています。