bzoj1799: [Ahoi2009]self 同类分布-白红宇

bzoj1799: [Ahoi2009]self 同类分布

阅读量：4957 次

发布时间：2019-06-12

本文共 1414 字，大约阅读时间需要 4 分钟。

数位dp

先从1到162枚举各位数之和

s[i][j][k][l]表示i位数，第一位小于等于j，当前各位数字和为k，当前取模余数为l的方案数

然后脑补一下转移就行了

详见代码

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #define ll long longusing namespace std;ll P;int bin[20];bool vis[20][180][180];ll s[20][10][180][180];ll f(int n,int t,int sum,int mod);void solve(int n,int sum,int mod){ if (n<1) return; if (vis[n][sum][mod]) return; vis[n][sum][mod]=1; for (int i=0;i<10;++i) s[n][i][sum][mod]=f(n-1,9,sum-i,(mod-bin[n]*i%P+P)%P); for (int i=1;i<10;++i) s[n][i][sum][mod]+=s[n][i-1][sum][mod];}ll f(int n,int t,int sum,int mod){ if (sum<0||n*9
           
            <0) return 0; if (n<1) return mod==0; solve(n,sum,mod); return s[n][t][sum][mod];}int a[21],b[21],len0,len1;int main(){ ll L,R; scanf("%lld%lld",&L,&R);++R; for (len0=0;L;L/=10) a[++len0]=L%10; for (len1=0;R;R/=10) b[++len1]=R%10; bin[1]=1; ll ans=0; for (P=1;P<=len1*9;++P){ for (int i=2;i<=len1;++i) bin[i]=bin[i-1]*10%P; ll ans0,ans1; memset(vis,0,sizeof(vis)); for (int k=0;k<2;++k){ swap(ans0,ans1);ans0=0; for (int i=1;i<=max(len0,len1);++i) swap(a[i],b[i]); swap(len0,len1); int now=P,nowmod=0; for (int i=len0;i;--i){ ans0+=f(i,a[i]-1,now,nowmod); now-=a[i];nowmod=(nowmod-a[i]*bin[i]%P+P)%P; } } ans+=ans1-ans0; } printf("%lld\n",ans); return 0;}