之前做网络赛的时候，看出来这是数位dp了，奈何自己不会数位dp，网上找了个数位dp计算回文数的模板也套错了 因为不会数位dp，也找不出是哪里的毛病。 现在学了数位dp，再来切这题。 这题和LightOJ 1205 Palindromic Numbers基本一样，就是多了个不同的进制。在lightoj 1205的基础上，再加一维表示不同的进制，然后数位dp即可。做的时候数组开小了，wa了好几发。。查了老半天才发现。。
#include <stdio.h> #include <string.h> typedef long long LL; LL dp[40][40][40]; int digit[35]; int assist[35]; int calc(int num, int k) { int len = 0; while(num) { digit[len++] = num%k; num /= k; } return len; } LL dfs(int i, int len, int e, int k) { if(i == -1) return 1; if(!e && ~dp[k][len][i]) return dp[k][len][i]; LL res = 0; int u = e?digit[i]:(k-1); for(int d = 0; d <= u; ++d) { assist[i] = d; if(i == len && d == 0) res += dfs(i-1,len-1,e&&d==u,k); else if(i < (len+1)/2 && d == assist[len-i]) res += dfs(i-1,len,e&&d==u,k); else if(i >= (len+1)/2) res += dfs(i-1,len,e&&d==u,k); } return e?res:dp[k][len][i]=res; } LL solve(int num, int k) { int len = calc(num,k); return dfs(len-1,len-1,1,k); } int main() { int T,L,R,l,r,time = 0; memset(dp,-1,sizeof(dp)); scanf("%d",&T); while(T--) { scanf("%d %d %d %d",&L,&R,&l,&r); LL num = R-L+1; LL res = 0; LL cnt = 0; for(int i = l; i <= r; ++i) { cnt = solve(R,i)-solve(L-1,i); res = res + num-cnt + cnt*(LL)i; } printf("Case #%d: %I64d\n",++time,res); } return 0; }