C - digitnum Editorial 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;
}

posted:
last update: