C - digitnum 解説 by physics0523
まず、各 \(f(x)\) の値を観察していきましょう。
- \(f(1)=1,f(2)=2, \dots ,f(9)=9\)
- \(f(10)=1,f(11)=2, \dots , f(99)=90\)
- \(f(100)=1,f(101)=2, \dots , f(999)=900\)
- \(\dots\)
なんとなく規則性は掴めたでしょうか?
では、実際に \(f(1)+f(2)+\dots+f(N)\) を求めていきましょう。
先ほどの観察を利用した、以下の解法が楽な方針でしょう。
- \(1\) 以上 \(\min(10-1,N)\) 以下の整数が \(K\) 個あるとき、答えに \(1+2+\dots+K\) を加算する。
- \(10\) 以上 \(\min(100-1,N)\) 以下の整数が \(K\) 個あるとき、答えに \(1+2+\dots+K\) を加算する。
- \(100\) 以上 \(\min(1000-1,N)\) 以下の整数が \(K\) 個あるとき、答えに \(1+2+\dots+K\) を加算する。
- \(\dots\)
一般には、以下の通りとなります。
- \(1\) 以上 \(18\) 以下の整数 \(k\) に対して、 \(10^{k-1}\) 以上 \(\min(10^k-1,N)\) 以下の整数が \(K\) 個あるとき、答えに \(1+2+\dots+K\) を加算する。
最後に、どのようにして \(1+2+\dots+K\) を求めればよいでしょうか。ここで、 \(K \le 9 \times 10^{17}\) であることと、 \(998244353\) (以降 \(M\) とする) で割った余りを問われていることに注意してください。
ひとまず余りをとることを気にしないものとすると、 \(1+2+\dots+K=\frac{K\times(K+1)}{2}\) となります。
まず、 \(K \times (K+1)\) を \(M\) で割った余りは、( \(K\) を \(M\) で割った余り) \(\times\) ( \((K+1)\) を \(M\) で割った余り) を \(M\) で割った余りと一致します。
では、 \(2\) で割る操作はどのようにすればよいでしょうか。
実は、 \(998244353\) で割った余りの世界では、 \(2\) で割る操作と \(499122177\) を掛ける操作とは等価です。(より詳しくは、 \(499122177\) は \(\mod 998244353\) における \(2\) の逆元です。詳しくは こちらの記事 も参考にしてください。)
類題:
ARC127-A
実装例(C++):
#include<bits/stdc++.h>
#define mod 998244353
#define inv2 499122177
using namespace std;
long long triangular_number(long long x){
x%=mod;
long long res=x;
res*=(x+1);res%=mod;
res*=inv2;res%=mod;
return res;
}
int main(){
long long n;
cin >> n;
long long res=0;
long long p10=10;
for(int dg=1;dg<=18;dg++){
long long l=p10/10;
long long r=min(n,p10-1);
if(l<=r){res+=triangular_number(r-l+1);res%=mod;}
p10*=10;
}
cout << res << '\n';
return 0;
}
投稿日時:
最終更新: