求1-n内，包含13且能够被13整除的数字的个数。 和 hdu 3555 Bomb相差不大，就是多了一个要整除的条件，那就再添加一个状态来标记是否能被13整除。然后数位dp即可。 不过在转移状态的时候，我搞错了 参考：http://blog.csdn.net/libin56842/article/details/10026063
#include <bits/stdc++.h> using namespace std; int dp[15][15][3]; int digit[11]; int len; void calc(int num) { len = 0; while(num) { digit[len++] = num%10; num /= 10; } } int dfs(int i, int mod, int s, bool e) { if(i == -1) return mod==0&&s==2; if(!e && ~dp[i][mod][s]) return dp[i][mod][s]; int res = 0; int u = e?digit[i]:9; for(int d = 0; d <= u; ++d) { int _mod = (mod*10+d)%13; int _s = s; if(s == 0 && d == 1) _s = 1; if(s == 1 && d != 1) _s = 0; if(s == 1 && d == 3) _s = 2; res += dfs(i-1,_mod,_s,e&&d==u); } return e?res:dp[i][mod][s]=res; } int solve(int num) { calc(num); return dfs(len-1,0,0,true); } int main() { int n; memset(dp,-1,sizeof(dp)); while(scanf("%d",&n) != EOF) printf("%d\n",solve(n)); return 0; }