统计区间 [1,n] 中含有 '13' 且模 13 为 0 的数字有多少个。
就是把情况用状态表示出来，几维不是问题，终点是把所有的状态表示出来。
转移就是枚举该位是多少，根据这个位是多少，改变下一个dfs的参数，转移到下一位就好
边界：注意只有当所有的情况都符合的时候，i==0时才能把方案数置为1，否则，就像这道题，如果到最后没有13，且余数不为0，那么就应该返回方案数0
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<cstdlib> using namespace std; int f[11][2][2][13]; int n,li[11]; int remain[11]; int dfs(int i,bool state,bool have,int k,bool limit) { if (i==0&&k==0&&have) return 1;//边界 if (i==0) return 0; if (!limit && f[i][state][have][k]) return f[i][state][have][k];//数位dp的limit必须加，因为，在边界最大值的情况是要注意处理的 int up=limit ? li[i]:9,ans=0; for (int j=0;j<=up;j++) { int h=((k-(j*remain[i]))%13+13)%13; ans+=dfs(i-1 , j==1?true:false , have||(state&&j==3) ? true:false, h , limit&& j==up?true :false ); } if (!limit) f[i][state][have][k]=ans;//相对应上面的limit return ans; } void work(int n) { memset(f,0,sizeof(f)); memset(li,0,sizeof(li)); int tot=0; while (n) { li[++tot]=n%10; n=n/10; } printf("%d\n",dfs(tot,false,false,0,true)); } int main() { remain[1]=1; for (int i=2;i<11;i++ ) remain[i]=remain[i-1]*10%13; while (scanf("%d",&n)!=EOF) work(n); return 0; }
