题解：P13046 [GCJ 2021 Finals] Divisible Divisions

LastKismet · 2025-11-13 16:16:38 · 题解

Sol

存在显然 DP 状态 f(i,0/1) 表示考虑前 i 个点分段，最后一段是不是倍数的方案数。显然可以 O(n^2) 转移。

假如 \gcd(d,10)=1，我们可以开桶前缀和做到 O(n)，具体的，s_r-10^{r-l}s_l\equiv0\pmod d\Rightarrow 10^{-r}s_r\equiv10^{-l}s_l\pmod d。然而当二者不互质时不存在逆元，就死掉了。

然而我们发现 10 的因数只有 1,2,5,10 四个，我们可以将模数 d 表示成 2^x5^ym 的形式，当 r-l\ge\max(x,y) 时，模 2^x,5^y 的结果均必然为 0，我们只需要考虑模 m 的结果即可，我们可以用同样的方法前缀和优化转移这部分，而后面几个暴力转移即可。最后复杂度是 O(TN\log D)。

Code

inline void Main(){
    cin>>s>>d;
    n=s.size();s=' '+s;
    rep(i,1,n)a[i]=s[i]-'0';
    rep(i,1,n)a[i]+=a[i-1]*10%d,a[i]%=d;
    repl(i,0,d)sum[i][0]=sum[i][1]=0;S=0;rep(i,1,n)f[i][0]=f[i][1]=0;
    ll m=d,m2=1,m5=1;
    while(!(m%2))m/=2,m2*=2;
    while(!(m%5))m/=5,m5*=5;
    pw[0]=1;rep(i,1,n)pw[i]=pw[i-1]*10%m;
    rep(i,0,n)exgcd(pw[i],m,iv[i],iv[i+1]),iv[i]=(iv[i]%m+m)%m;
    f[0][1]=1;
    rep(i,1,n){
        ll t=10%d;
        per(j,i-1,max(i-20,0)){
            if((a[i]-a[j]*t%d+d)%d==0)f[i][1]+=f[j][0]+f[j][1];
            else f[i][0]+=f[j][1];
            t*=10,t%=d;
        }
        if(a[i]%m2==0&&a[i]%m5==0)
            f[i][1]+=sum[a[i]*iv[i]%m][0]+sum[a[i]*iv[i]%m][1],
            f[i][0]+=S-sum[a[i]*iv[i]%m][1];
        else f[i][0]+=S;
        if(i-20>=0)S+=f[i-20][1],sum[a[i-20]*iv[i-20]%m][0]+=f[i-20][0],sum[a[i-20]*iv[i-20]%m][1]+=f[i-20][1];
    }
    put(f[n][0]+f[n][1]);
}