题解 CF756F【Long number】

xtx1092515503 · 2022-05-12 19:31:22 · 题解

第一眼看上去：这么多范式定义，显然是大模拟，大模拟放 div1F，这场没救了。

然后就开始写大模拟了。对于每段我们可以用一个二元组 (val,ten) 描述之，表示这段取模后的值是 val，这段长度关于 10 的幂次是 ten。合并两个二元组是简单的；对一个二元组重复若干次可以类快速幂（只不过是以 10 为底）地处理。

然后写到 l-r 这个操作就给我整不会了。

我们首先把它做一步差分，变成 1-r 除去 1-l 再加上 l 自身。二元组显然是可以支持求逆的。

于是我们现在就只需要会求 1-x 拼接的结果即可。

把它再做一步转换，变成位数小于 x 的东西拼接成位数等于 x 的东西。

先看前者。这是可以预处理的，我们预处理 f_x 表示位数不超过 x 的元素拼接成的二元组。

考虑由 f_x 推出 f_{x+1}。这要把位数为 x+1 的东西全部考虑到。

考虑把 val 和 ten 分开算。

对于 ten，其显然就是 (10^{x+1})^{10^{x+1}-10^x}。

对于 val，我们要求的是 \sum\limits_{i=10^x}^{10^{x+1}-1}i(10^{x+1})^{10^{x+1}-i-1}。

把它做一步差分变成 \sum\limits_{i=0}^{10^{x+1}-1}i(10^{x+1})^{10^{x+1}-i-1}-\sum\limits_{i=0}^{10^x-1}i(10^{x+1})^{10^{x+1}-i-1}。

把它抽象成 \sum\limits_{i=0}^{n-1}ia^i 这个模型。而这个模型是经典的。

根据该性质，我们可以大力算快速幂，用欧拉定理处理指数上的东西，并在 O(\log n) 的时间内从 f_x 推到 f_{x+1}。

然后我们就只需计算位数等于 x 的东西了。运用我们上面的分析流程，这是简单的。

考虑分析复杂度。我们可以在 O(n\log n) 的时间内预处理出 f，在 O(|s|\log n) 的时间内处理出一段 l-r。预先建出表达式树，总复杂度可以做到 O(n\log n)。

（我觉得这题出题人阴间的地方就是，你明明直接出 l-r 就好了，为什么还要套一堆表达式处理的细节）

代码：

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int phi=mod-1;
int ksm(int x,int y=phi-1){int z=1;for(;y;y>>=1,x=1ll*x*x%mod)if(y&1)z=1ll*z*x%mod;return z;}
int msk(int x,int y){int z=1;for(;y;y>>=1,x=1ll*x*x%phi)if(y&1)z=1ll*z*x%phi;return z;}
struct dat{
int val,ten;
dat(){val=0,ten=1;}
dat(int V,int T){val=V,ten=T;}
friend dat operator+(const dat&u,const dat&v){return dat((1ll*u.val*v.ten+v.val)%mod,1ll*u.ten*v.ten%mod);}
friend dat operator-(const dat&u,const dat&v){
    dat w;
    w.ten=1ll*u.ten*ksm(v.ten)%mod;
    w.val=(u.val+mod-1ll*v.val*w.ten%mod)%mod;
    return w;
}
void print()const{printf("[%d,%d]",val,ten);}
}f[100100];
dat ksm(dat x,int y){dat z;for(;y;y>>=1,x=x+x)if(y&1)z=z+x;return z;}
dat KSM(char*l,char*r,dat d){
    static dat pov[10];for(int i=1;i<10;i++)pov[i]=pov[i-1]+d;
    dat ret;
    while(l!=r)ret=ksm(ret,10)+pov[*(l++)-'0'];
    return ret;
}
dat gene(char*l,char*r){
    dat ret;ret.ten=ksm(10,r-l);
    while(l!=r)ret.val=(10ll*ret.val+*(l++)-'0')%mod;
    return ret;
}
int stereotype(int a,int modn,int phin){
    // printf("STER:%d,%d,%d\n",a,modn,phin);
    int an=ksm(a,phin);
    int ia1=ksm((a+mod-1)%mod);
    return (1ll*(modn+mod-1)*an-1ll*(an+mod-1)*ia1%mod+mod+1)%mod*ia1%mod;
}
dat conca(char*l,char*r){
    int modn=0,phin=0;
    for(char*i=l;i!=r;i++)modn=(10ll*modn+(*i-'0'))%mod,phin=(10ll*phin+(*i-'0'))%phi;
    (++modn)%=mod,(++phin)%=phi;
    int i=r-l-1;
    int fv=stereotype(ksm(10,phi-(i+1)),modn,phin);
    int rv=stereotype(ksm(10,phi-(i+1)),ksm(10,i),msk(10,i));
    int val=1ll*(fv+mod-rv)*ksm(ksm(10,i+1),(phin+phi-1)%phi)%mod;
    int ten=ksm(ksm(10,i+1),(phin+phi-msk(10,i))%phi);
    // for(char*i=l;i!=r;i++)putchar(*i);printf(":"),(f[i]+dat(val,ten)).print();puts("");
    return f[i]+dat(val,ten);
}
int S,mat[100100],stk[100100],tp;
char s[100100];
dat solve(int l,int r){
    // printf("SOLVE:[%d,%d]",l,r);for(int i=l;i<r;i++)putchar(s[i]);puts("");
    if(l>=r)return dat();
    int p=l;while(s[p]>='0'&&s[p]<='9')p++;
    if(p==r)return gene(s+l,s+r);
    if(s[p]=='(')return KSM(s+l,s+p,solve(p+1,mat[p]))+solve(mat[p]+2,r);
    if(s[p]=='+')return gene(s+l,s+p)+solve(p+1,r);
    if(s[p]=='-'){
        int q=p+1;
        while(s[q]>='0'&&s[q]<='9')q++;
        return (gene(s+l,s+p)+(conca(s+p+1,s+q)-conca(s+l,s+p)))+solve(q+1,r);
    }
}
int main(){
    scanf("%s",s),S=strlen(s);
    for(int i=0;i<S;i++){
        int fv=stereotype(ksm(10,phi-(i+1)),ksm(10,i+1),msk(10,i+1));
        int rv=stereotype(ksm(10,phi-(i+1)),ksm(10,i),msk(10,i));
        int val=1ll*(fv+mod-rv)*ksm(ksm(10,i+1),(msk(10,i+1)+phi-1)%phi)%mod;
        int ten=ksm(ksm(10,i+1),(msk(10,i+1)+phi-msk(10,i))%phi);
        f[i+1]=f[i]+dat(val,ten);
    }
    for(int i=0;i<S;i++){
        if(s[i]=='(')stk[++tp]=i;
        if(s[i]==')')mat[stk[tp]]=i,mat[i]=stk[tp--];
    }
    printf("%d\n",solve(0,S).val);
    return 0;
}