公式

G - 88888888 解説 by en_translator


Suppose \(N\) has \(K\) digits, and let \(P=998244353\).
Then \(V_N\) can be represented as \(V_N=N+N\cdot 10^K+N\cdot 10^{2K}+\cdots+N\cdot 10^{(N-1)K}\).

It can be written as \(V_N=N(1+10^K+10^{2K}+\cdots+10^{(N-1)K})=\frac{N(10^{NK}-1)}{10^K-1}\). Here, \(K\) ranges between \(1\) and \(19\), none of which makes \(10^K-1\) a multiple of \(P\). Since \(P\) is a prime, there exists unique \(1\leq R_K\leq P-1\) such that \(R_K(10^K-1)\equiv 1\pmod{P}\).
Then, \(NR_K(10^{NK}-1)\) and \(\frac{N(10^{NK}-1)}{10^K-1}\) has the same remainder divided by \(P\), so it is sufficient to find the remainder of \(NR_K(10^{NK}-1)\) divided by \(P\). One can use modint of AtCoder Library to find it, for instance. (If you want to implement it by yourself, you can use \(R_K\equiv(10^K-1)^{P-2} \pmod{P}\) by Fermat’s little theorem.) The complexity is \(O(\log( NK)+\log P)\), which is fast enough.
Thus, the problem has been solved.

Sample code in 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;
}

投稿日時:
最終更新: