题目：求1～n的范围里含有13且能被13整除的数字的个数。
分析：
dfs(len, num, mod, flag)
mod记录数字对13取余后的值
len表示当前位数
num＝＝0 不含13且上一位不为1
pre＝＝1 不含13且上一位为1
pre＝＝2 含13
flag表示是否可以任意取值(判断范围)。
如此，记忆化搜索即可得解。
总结：我是在最后才判断是否可以%13 , 但是这是不可以的 ， 经过这道题后，理解更好了 ；
这里有个式子特别重要 ： 关于连加取mod , 例如： 123%13=（100+20+3）%13 = （（1%13*10+2）%13*10+3）%13； ！！！！！ 这在数位dp很重要
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <cstdlib> #include <vector> using namespace std; #define LL long long #define MOD 13 LL dp[20][3][13]; int dis[20]; LL dfs(int len, int type, int mod, bool flag) { if(len < 0) return type == 2 && mod == 0; if(!flag && dp[len][type][mod]!=-1) return dp[len][type][mod]; int end = flag?dis[len]:9; int ans = 0; for(int i=0; i<=end; i++) { if(type == 2 || (type == 1 && i == 3)) ans += dfs(len-1, 2, (mod*10+i)%MOD, flag&&i==end); else ans += dfs(len-1, i==1?1:0, (mod*10+i)%MOD, flag&&i==end); } if(!flag) dp[len][type][mod] = ans; return ans; } LL solve(LL n) { int len = 0; while(n) { dis[len++] = n%10; n /= 10; } return dfs(len-1, 0, 0, 1); } int main() { int n; memset(dp, -1, sizeof(dp)); while(cin>>n) cout<<solve(n)<<endl; return 0; }