题解 P4127 【[AHOI2009]同类分布】

这是一篇有些赖皮的题解 （如果不赖皮的话，bzoj上也是能卡过去的） 首先由于我这个非常$sb$的方法复杂度高达$O(171^4)$，所以面对极限的$1e18$的数据实在是卡死了 但是这个时候可以骗一下 一般来说肯定会有一个点的数据到达了$1e18$，所以我们先将$1$到$1e18$之间的答案算出来，这样再去算另一个左边界的话至少可以节省一半的常数，就算左边界不是很小也有可能还算点希望 如果左边界特别小的话，可能就能幸运的卡过去 这道题的左边界就非常小啊，我估计不超过$1e6$ 于是就卡过去了 再来看看我这个非常$sb$的dp，我觉得可能没有人这么写 我们设$dp[i][j][s][k]$**表示一个数填到了$i$位，最高位填的是$j$，数位和是$s$**，且**这些数中对于某一个数取模得$k$的数的个数** 至于这个某一个数是什么，我们当然是要最外面套上一个枚举数位和了 那么答案很简单啊，如果我们当前枚举的数位和是$x$的话，答案肯定就跟$dp[][][x][0]$有关系了 那么这个方程怎么转移呢 显然有 $$dp[i+1][p][j+p][(p*10^i+k)\%x]=\sum_{t=0}^9dp[i][t][j][k]$$ $t$表示上一位填的数，$i$是位数，$p$是这一位填的数，$j$是数位和，$k$是对当前枚举的数位和取模之后的值，$x$表示当前枚举的数位和 同时我们发现好像直接去枚举$t$有些奢侈，我们可以直接把$\sum_{t=0}^9dp[i][t][j][k]$算好，于是我用$dp[i][10][j][t]$来存下来$\sum_{t=0}^9dp[i][t][j][k]$，这样就可以优化转移了 之后就是数位$dp$的套路卡上界了，大概就是注意一下卡上界的时候存一下前面的数位和 复杂度大概是$O((log_{10}n*9)^4)$，确实这是一个很垃圾的复杂度 代码 ```cpp #include<iostream> #include<cstring> #include<cstdio> #define re register #define maxn 172 #define LL long long #define max(a,b) ((a)>(b)?(a):(b)) #define min(a,b) ((a)<(b)?(a):(b)) LL dp[20][11][maxn][maxn]; LL L,R; LL ans; int num[2],a[20][2]; LL base[20]; LL mod; inline LL qm(LL x) {return x>=mod?x-mod:x;}//优化一下取模 inline void spilt(LL x,int pd) { num[pd]=0; while(x) a[++num[pd]][pd]=x%10,x/=10; }//分解数位 inline void work(int x,int Len) { mod=x; memset(dp,0,sizeof(dp)); for(re int i=0;i<=9;++i) dp[1][i][i][qm(i)]+=1,dp[1][10][i][qm(i)]+=1; for(re int i=1;i<Len;++i)//枚举长度 for(re int j=0;j<=min(x,i*9);++j)//枚举数位和 for(re int k=0;k<x;++k)//枚举对当前枚举的数位和x取模后的值 { if(!dp[i][10][j][k]) continue; for(re int p=0;p<=9;++p) dp[i+1][p][j+p][(p*base[i]+k)%x]+=dp[i][10][j][k],dp[i+1][10][j+p][(p*base[i]+k)%x]+=dp[i][10][j][k]; } } inline LL slove(int pd,int x) { LL tot=0; for(re int i=1;i<num[pd];++i) tot+=dp[i][10][x][0]-dp[i][0][x][0];//统计所有位数小于给定数的，注意首位不能填0 for(re int i=1;i<a[num[pd]][pd];++i) tot+=dp[num[pd]][i][x][0];//统计所有位数和给定数相同的，但是最高位小于给定数的 LL now=a[num[pd]][pd],cnt=now; //now表示前面所有的数位和，cnt表示前面的数的值是多少 //（比如说12345,卡到三这一位上，now=1+2=3，cnt=1*10+2*1=12） if(x-now<0) return tot; for(re int i=num[pd]-1;i;--i)//当前不同的那一位,[i+1,num]与x完全相同 { LL t=qm(x-cnt*base[i]%x);//根据算出后面的数位所需要的余数是多少 for(re int j=0;j<a[i][pd];j++) tot+=dp[i][j][x-now][t]; //当前第i位可以填的数必须要小于给定数当前的这一位，这里就按照dp的方式来统计答案 now+=a[i][pd]; cnt=cnt*10+a[i][pd]; cnt=qm(cnt); if(x-now<0) break; } return tot; } int main() { scanf("%lld%lld",&L,&R); spilt(L,0),spilt(R+1,1); base[0]=1; for(re int i=1;i<=18;++i) base[i]=base[i-1]*10; if(R==1000000000000000000) { ans+=29410615796612778; for(re int i=1;i<=num[0]*9;++i) work(i,num[0]),ans-=slove(0,i); printf("%lld\n",ans); return 0; }//去掉这个if在bzoj上也能卡过去 for(re int i=1;i<=num[1]*9;++i)//枚举数位和 work(i,num[1]),ans+=slove(1,i)-slove(0,i); printf("%lld\n",ans); return 0; } ```