数位dp之B-number

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 int a[20];
 7 int dp[20][20][3];
 8 /*
 9 dp[i][j][k] j表示余数
10 k==0不包含13且不以1结尾
11 k==1 不包含13且1结尾
12 k==2 包含13
13 */
14 int dfs(int pos,int mod,int sta,bool lim){
15     if(pos<=0)
16         return mod==0&&sta == 2;
17     if(!lim&&dp[pos][mod][sta]!=-1)
18         return dp[pos][mod][sta];
19     int up = lim ? a[pos] : 9;
20     int ans = 0;
21     for (int i = 0; i <= up;i++)
22     {
23         int mod1 = (mod * 10 + i) % 13;//计算余数
24         int sta1 = sta;
25         if(sta==1&&i==3)
26             sta1 = 2;
27         else if(sta==0&&i==1)
28             sta1 = 1;
29         else if(sta==1&&i!=1)
30             sta1 = 0;
31         ans += dfs(pos - 1, mod1,sta1, lim && i == up);
32     }
33     if(!lim){
34         dp[pos][mod][sta] = ans;
35     }
36     return ans;
37 }
38 int solve(int x){//计算数各个位置上的值
39     int pos = 0;
40     while(x){
41         a[++pos] = x % 10;
42         x /= 10;
43     }
44     return dfs(pos,0, 0, true);
45 }
46 int main(){
47     int r;
48     while(~scanf("%d",&r)){
49         memset(dp, -1, sizeof dp);
50         printf("%d\n", solve(r));
51     }
52 }