CF1601F Two Sorts 题解--zhengjun

· · 题解

link

这里提供一种不用 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 的位数，直接计算个数即可。

时间复杂度

总结步骤：

总时间复杂度：O(\frac{n}{p}\log^3 n)，常数很小，跑得飞快，也很好写，暂时是 CF 最优解。

代码

#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;
}