DOJ Beginner Contest 9 G - Pi Problem
- サイト
- DOJ
- コンテスト
- DOJ Beginner Contest 9
- 問題
- G - Pi Problem
正の整数 に対して、 の十進表記を 回つなげた整数を とします。たとえば です。
長さ の正整数列 が与えられるので、
を で割った余りを求める問題です。 で、 の総和は 以下です。
rep を式で表す
Section titled “rep を式で表す”が 桁のとき、 を 回つなげることは、 に を掛けることと同じです。等比数列の和を使うと
です。以下、 桁の数を 回つなげたときに掛かる部分を と書きます。
積を 2 つに分ける
Section titled “積を 2 つに分ける”の桁数を とすると、求める積は
と分けられます。
前半では、 は自分より後ろの の個数だけ掛かるので、 です。
後半は、 ごとにまとめます。 なので桁数 は から までしかありません。 で桁数が のものの個数を とすると、後半は
です。 は桁数ごとの個数を数えながら を動かせば求まります。 は つの につき 通りしかないので、全体で 回程度の計算で済みます。
は割り算を含みます。 の逆元を使ってもよいのですが、解答コードでは逆元を使わずに計算しています。
、、 とします。 は で割り切れます。 を で割った余りを とすると、 と書けて、 も で割り切れます。両辺を で割ると
なので、 を で割った余りは を で割った余りと同じです。つまり、 を を法として計算し、 を引いてから で割れば、 を で割った余りが求まります。
Python
MOD = 998244353for _ 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] が「自分より前にある 桁の数の個数」になるようにしています。