题解：P16140 圆圈函数（circle）
Dreamer_002 · · 题解
动态规划好题。
思路
- 注意到数据范围较大，又注意到题目中问的是可行自然数个数，因此宜用动态规划来解题。
- 第一：发现无论
m 的个位是几，都不会有影响，即若f(10k)+f(n)=f(10k+10n) ，则f(10k+a)+f(n)=f(10k+a+10n) ，其中0 \leq a \leq 9 。 - 第二：记
g(m)=f(10n+m)-f(n)-f(m) ，则即求使g(m)=0 的m 的个数。 - 第三：定义状态数组
dp_{i,j} 表示当0 \leq m \leq 10^{i+1}-1 ，且满足g(m)=j 的m 的个数，以此可以进行状态转移。 - 第四：发现可能存在进位，于是将
dp_{i,j} 拆成两个状态：dp_{i,j,0} 和dp_{i,j,1} ，前者表示在之前条件的基础上，还要满足当前位对下一位没有进位的条件的m 的个数，后者则反之。 - 第五：发现有高位限制，即
m \leq n ，于是将dp_{i,j,k} 拆成两个状态：dp_{i,j,k,0} 和dp_{i,j,k,1} ，前者表示在之前条件的基础上，还要满足当前填的m 不超过n 的后i+1 位的10 倍，即m \leq 10(n \mod 10^{i+1}) 的m 的个数，后者则反之。 - 第六：发现前导
0 会影响g(m) ，因此将dp_{i,j,k,l} 拆成i 个状态：dp_{i,j,k,l,a} ，表示在之前条件的基础上，还要满足恰好有a 个前导0 的条件的m 的个数。 - 第七：正常推导时，前导
0 计入贡献统计，只有在统计最终答案时，才考虑前导0 。 - 第八：整体用背包思想实现。
代码
//code by Dreamer_002 //作者实力有限（太菜），代码略长，敬请谅解 #include<cstdio>//long long const long long N = 20; const long long F[10]={1,0,0,0,1,0,1,0,2,1}; long long n,tn,nn,num[N],dp[N][N*4][2][2][N];//+40 防止在 g(m)<0 时溢出 int main(){ // freopen("P16140.in","r",stdin); // freopen("P16140.out","w",stdout); scanf("%lld",&n);tn=n; while(tn>0){ nn++; num[nn]=tn%10; tn/=10; } dp[0][40][0][0][0]=num[1]+1; dp[0][40][0][1][0]=9-num[1]; dp[0][40][1][0][0]=0; dp[0][40][1][1][0]=0; for(long long i=1;i<=nn-1;i++){ for(long long j=0;j<=9;j++){//这里指当前位填什么 if(j==0){//前导0 for(long long k=4;k<=76;k++){ for(long long a=1;a<=i;a++){ if(num[i]+j<=9){ if(j<num[i+1]){ dp[i][k][0][0][a]+=dp[i-1][k-(F[num[i]+j]-F[num[i]]-F[j])][0][0][a-1]; dp[i][k][0][0][a]+=dp[i-1][k-(F[num[i]+j]-F[num[i]]-F[j])][0][1][a-1]; } else if(j==num[i+1]){ dp[i][k][0][0][a]+=dp[i-1][k-(F[num[i]+j]-F[num[i]]-F[j])][0][0][a-1]; dp[i][k][0][1][a]+=dp[i-1][k-(F[num[i]+j]-F[num[i]]-F[j])][0][1][a-1]; } else if(j>num[i+1]){ dp[i][k][0][1][a]+=dp[i-1][k-(F[num[i]+j]-F[num[i]]-F[j])][0][0][a-1]; dp[i][k][0][1][a]+=dp[i-1][k-(F[num[i]+j]-F[num[i]]-F[j])][0][1][a-1]; } } else{ if(j<num[i+1]){ dp[i][k][1][0][a]+=dp[i-1][k-(F[num[i]+j-10]-F[num[i]]-F[j])][0][0][a-1]; dp[i][k][1][0][a]+=dp[i-1][k-(F[num[i]+j-10]-F[num[i]]-F[j])][0][1][a-1]; } else if(j==num[i+1]){ dp[i][k][1][0][a]+=dp[i-1][k-(F[num[i]+j-10]-F[num[i]]-F[j])][0][0][a-1]; dp[i][k][1][1][a]+=dp[i-1][k-(F[num[i]+j-10]-F[num[i]]-F[j])][0][1][a-1]; } else if(j>num[i+1]){ dp[i][k][1][1][a]+=dp[i-1][k-(F[num[i]+j-10]-F[num[i]]-F[j])][0][0][a-1]; dp[i][k][1][1][a]+=dp[i-1][k-(F[num[i]+j-10]-F[num[i]]-F[j])][0][1][a-1]; } } if(num[i]+j+1<=9){ if(j<num[i+1]){ dp[i][k][0][0][a]+=dp[i-1][k-(F[num[i]+j+1]-F[num[i]]-F[j])][1][0][a-1]; dp[i][k][0][0][a]+=dp[i-1][k-(F[num[i]+j+1]-F[num[i]]-F[j])][1][1][a-1]; } else if(j==num[i+1]){ dp[i][k][0][0][a]+=dp[i-1][k-(F[num[i]+j+1]-F[num[i]]-F[j])][1][0][a-1]; dp[i][k][0][1][a]+=dp[i-1][k-(F[num[i]+j+1]-F[num[i]]-F[j])][1][1][a-1]; } else if(j>num[i+1]){ dp[i][k][0][1][a]+=dp[i-1][k-(F[num[i]+j+1]-F[num[i]]-F[j])][1][0][a-1]; dp[i][k][0][1][a]+=dp[i-1][k-(F[num[i]+j+1]-F[num[i]]-F[j])][1][1][a-1]; } } else{ if(j<num[i+1]){ dp[i][k][1][0][a]+=dp[i-1][k-(F[num[i]+j+1-10]-F[num[i]]-F[j])][1][0][a-1]; dp[i][k][1][0][a]+=dp[i-1][k-(F[num[i]+j+1-10]-F[num[i]]-F[j])][1][1][a-1]; } else if(j==num[i+1]){ dp[i][k][1][0][a]+=dp[i-1][k-(F[num[i]+j+1-10]-F[num[i]]-F[j])][1][0][a-1]; dp[i][k][1][1][a]+=dp[i-1][k-(F[num[i]+j+1-10]-F[num[i]]-F[j])][1][1][a-1]; } else if(j>num[i+1]){ dp[i][k][1][1][a]+=dp[i-1][k-(F[num[i]+j+1-10]-F[num[i]]-F[j])][1][0][a-1]; dp[i][k][1][1][a]+=dp[i-1][k-(F[num[i]+j+1-10]-F[num[i]]-F[j])][1][1][a-1]; } } } } } else{ for(long long k=4;k<=76;k++){ for(long long a=0;a<i;a++){ if(num[i]+j<=9){ if(j<num[i+1]){ dp[i][k][0][0][0]+=dp[i-1][k-(F[num[i]+j]-F[num[i]]-F[j])][0][0][a]; dp[i][k][0][0][0]+=dp[i-1][k-(F[num[i]+j]-F[num[i]]-F[j])][0][1][a]; } else if(j==num[i+1]){ dp[i][k][0][0][0]+=dp[i-1][k-(F[num[i]+j]-F[num[i]]-F[j])][0][0][a]; dp[i][k][0][1][0]+=dp[i-1][k-(F[num[i]+j]-F[num[i]]-F[j])][0][1][a]; } else if(j>num[i+1]){ dp[i][k][0][1][0]+=dp[i-1][k-(F[num[i]+j]-F[num[i]]-F[j])][0][0][a]; dp[i][k][0][1][0]+=dp[i-1][k-(F[num[i]+j]-F[num[i]]-F[j])][0][1][a]; } } else{ if(j<num[i+1]){ dp[i][k][1][0][0]+=dp[i-1][k-(F[num[i]+j-10]-F[num[i]]-F[j])][0][0][a]; dp[i][k][1][0][0]+=dp[i-1][k-(F[num[i]+j-10]-F[num[i]]-F[j])][0][1][a]; } else if(j==num[i+1]){ dp[i][k][1][0][0]+=dp[i-1][k-(F[num[i]+j-10]-F[num[i]]-F[j])][0][0][a]; dp[i][k][1][1][0]+=dp[i-1][k-(F[num[i]+j-10]-F[num[i]]-F[j])][0][1][a]; } else if(j>num[i+1]){ dp[i][k][1][1][0]+=dp[i-1][k-(F[num[i]+j-10]-F[num[i]]-F[j])][0][0][a]; dp[i][k][1][1][0]+=dp[i-1][k-(F[num[i]+j-10]-F[num[i]]-F[j])][0][1][a]; } } if(num[i]+j+1<=9){ if(j<num[i+1]){ dp[i][k][0][0][0]+=dp[i-1][k-(F[num[i]+j+1]-F[num[i]]-F[j])][1][0][a]; dp[i][k][0][0][0]+=dp[i-1][k-(F[num[i]+j+1]-F[num[i]]-F[j])][1][1][a]; } else if(j==num[i+1]){ dp[i][k][0][0][0]+=dp[i-1][k-(F[num[i]+j+1]-F[num[i]]-F[j])][1][0][a]; dp[i][k][0][1][0]+=dp[i-1][k-(F[num[i]+j+1]-F[num[i]]-F[j])][1][1][a]; } else if(j>num[i+1]){ dp[i][k][0][1][0]+=dp[i-1][k-(F[num[i]+j+1]-F[num[i]]-F[j])][1][0][a]; dp[i][k][0][1][0]+=dp[i-1][k-(F[num[i]+j+1]-F[num[i]]-F[j])][1][1][a]; } } else{ if(j<num[i+1]){ dp[i][k][1][0][0]+=dp[i-1][k-(F[num[i]+j+1-10]-F[num[i]]-F[j])][1][0][a]; dp[i][k][1][0][0]+=dp[i-1][k-(F[num[i]+j+1-10]-F[num[i]]-F[j])][1][1][a]; } else if(j==num[i+1]){ dp[i][k][1][0][0]+=dp[i-1][k-(F[num[i]+j+1-10]-F[num[i]]-F[j])][1][0][a]; dp[i][k][1][1][0]+=dp[i-1][k-(F[num[i]+j+1-10]-F[num[i]]-F[j])][1][1][a]; } else if(j>num[i+1]){ dp[i][k][1][1][0]+=dp[i-1][k-(F[num[i]+j+1-10]-F[num[i]]-F[j])][1][0][a]; dp[i][k][1][1][0]+=dp[i-1][k-(F[num[i]+j+1-10]-F[num[i]]-F[j])][1][1][a]; } } } } } } } long long ans=0; for(long long a=0;a<nn;a++){ ans+=dp[nn-1][40-a][0][0][a];//这里统计答案时在计算前导0的影响 } if(num[nn]<9){ for(long long a=0;a<nn;a++){ ans+=dp[nn-1][40-a-(F[num[nn]+1]-F[num[nn]])][1][0][a];//这里统计答案时在计算前导0的影响 } } else{ for(long long a=0;a<nn;a++){ ans+=dp[nn-1][40-a][1][0][a];//这里统计答案时在计算前导0的影响 } } printf("%lld\n",ans); // fclose(stdin);fclose(stdout); return 0; }总结
从一开始的简单状态，到不断拆状态，这是一道数位动规与背包动规思想融合的好题，希望大家也能细细理解拆状态的过程与原因，终。