公式

G - 88888888 解説 by mechanicalpenciI


\(N\) の桁数を \(K\) 、また \(P=998244353\) とします。
このとき、\(V_N\) を 式で表すと、\(V_N=N+N\cdot 10^K+N\cdot 10^{2K}+\cdots+N\cdot 10^{(N-1)K}\) と書けます。

これを整理すると、 \(V_N=N(1+10^K+10^{2K}+\cdots+10^{(N-1)K})=\frac{N(10^{NK}-1)}{10^K-1}\) となります。 ここで、\(K\) の取り得る範囲は \(1\) 以上 \(19\) 以下ですが、この中に \(10^K-1\)\(P\) の倍数となるようなものはありません。よって、 \(P\) が素数であることに注意すると、\(R_K(10^K-1)\equiv 1\pmod{P}\) となるような \(1\leq R_K\leq P-1\) がただ一つ存在します。
このとき、\(NR_K(10^{NK}-1)\)\(\frac{N(10^{NK}-1)}{10^K-1}\)\(P\) で割った余りが等しいため、\(NR_K(10^{NK}-1)\). を \(P\) で割った余りを計算すれば良いです。これは例えば AtCoder Library の modint を用いて計算することができます。(自身で計算する際はフェルマーの小定理より \(R_K\equiv(10^K-1)^{P-2} \pmod{P}\) などを用いれば良いです。)計算量は \(O(\log( NK)+\log P)\) であり、十分高速です。
よってこの問題を解くことができました。

c++ による実装例:

#include <bits/stdc++.h>
#include <atcoder/modint>

using namespace std;
using namespace atcoder;
using mint = modint998244353;

int main() {
	long long n,x;
	mint r = 1;

	cin>>n;
	x=n;
	while(x){
		x/=10;
		r*=mint(10);
	}
    
	mint ans=mint(n)*(r.pow(n)-mint(1))*((r-mint(1)).inv());
	cout<<(ans.val())<<endl;
	return 0;
}

投稿日時:
最終更新: