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;
}
投稿日時:
最終更新: