这里提供一种不用 meet in middle 的方法，速度比较可观。
发现性质
开始简单的推一下式子。
\(\sum (i-a_i)\bmod p=\sum (rk_i-i+p\times\lfloor\frac{rk_i-i}{p}\rfloor)=p\times \sum\lfloor\frac{rk_i-i}{p}\rfloor,p=998244353\)
于是，只需求出 \(\sum\lfloor\frac{rk_i-i}{p}\rfloor\) 即可。
由于 \(p\) 达到了 \(10^9\) 级别，而且 \(rk_i-i\in [-n,n]\)。
所以 \(\lfloor\frac{rk_i-i}{p}\rfloor\) 在 \(O(\frac{n}{p})\) 级别。
转化问题
考虑枚举 \(k=\lfloor\frac{rk_i-i}{p}\rfloor\)，计算符合条件的 \(i\) 的个数。
对于 \(i\) 的限制即为：\(k\times p \le rk_i-i < (k+1)\times p\)。
直接差分掉，问题转化为求出 \(rk_i-i \le lim\) 的 \(i\) 的个数。
再发现性质
对于位数相同的数 \(i-1,i\)，发现字典序大小即为数值本身的大小。
所以 $rk_{i-1} +1 \le rk_{i}\iff rk_{i-1}-(i-1)\le rk_i -i $。
发现 \(rk_i-i\) 在相同位数的时候是递增的。
最后
于是，我们可以先枚举 \(i\) 的位数 \(len\)。
然后二分出该位数下满足 \(rk_i-i < lim\) 的最大的 \(i\) 即可。
还留下来最后一个问题，如何求出 \(rk_i\)？
计算 \(str(j)<str(i)\) 的个数，可以枚举 \(j\) 的位数，直接计算个数即可。
时间复杂度
总结步骤：
-
枚举 \(k=\lfloor\frac{rk_i-i}{p}\rfloor,O(\frac{n}{p})\)
-
枚举 \(i\) 的位数，\(O(\log n)\)
-
二分 \(i\)，\(O(\log n)\)
-
计算 \(rk_i\)，即枚举 \(j\) 的位数，\(O(\log n)\)
总时间复杂度：\(O(\frac{n}{p}\log^3 n)\)，常数很小，跑得飞快
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
using ll=long long;
const int N=20,p=998244353,mod=1e9+7;
char num[N];
int len;
ll n,pw[N];
int k,a[N];
ll getrk(ll x){
k=0;
for(ll y=x;y;y/=10)a[++k]=y%10;
for(int i=k+1;i<=len;i++)a[i]=0;
reverse(a+1,a+1+k);
ll now=0,ans=0;
for(int i=1;i<k;i++){
now=now*10+a[i];
ans+=now-pw[i-1]+1;
}
for(int i=k;i<len;i++){
now=now*10+a[i];
ans+=now-pw[i-1];
}
now=now*10+a[len];
if(now<=n)ans+=now-pw[len-1];
else ans+=n-pw[len-1]+1;
// fprintf(stderr,"getrk %lld %lld\n",x,ans+1);
return ans+1;
}
ll query(ll lim){
ll ans=0;
for(int i=1;i<=len;i++){
ll l=pw[i-1]-1,r=min(pw[i],n+1),mid;
for(;l+1<r;){
mid=(l+r)>>1;
if(getrk(mid)-mid<lim)l=mid;
else r=mid;
}
ans+=l-pw[i-1]+1;
}
// cerr<<"query "<<lim<<' '<<ans<<endl;
return ans;
}
signed main(){
scanf("%s",num+1),len=strlen(num+1);
for(int i=1;i<=len;i++)n=n*10+num[i]-'0';
for(int i=pw[0]=1;i<=len;i++)pw[i]=pw[i-1]*10;
ll las=0,ans=0;
for(ll k=-n/p-1;k*p<=n;k++){
ll cnt=query((k+1)*p);
ans-=k*(cnt-las),las=cnt;
}
cout<<(ans%mod*p%mod+mod)%mod;
return 0;
}