HDU 3652——B-number

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=3652

题意：让你找小于等于n的数里有多少个数里含'13‘而且可以被13整除

一看是否含13，数位dp，再往后看，可以被13整除，这咋做嘛

别慌，数位dp也是ok的，除了用%判断是否整除，我们还能怎么搞？而且是按位来算的

想到了吗，模拟除法呀，这样我们只需要存上次计算的余数就可以了（算是一个状态），当含13且能被13整除答案才累加

再来一个状态存是否含13就可以了

dp[pos][num][mod] 状态为 dp[当前搜到第几位][是否含13][上一位的余数]

num=0 啥也不是

num=1 上一位是1

num=2 含13

上代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 ll a[1000009];
 5 ll dp[20][3][19];
 6 ll check(ll num,ll i)
 7 {
 8     if(num==0&&i==1||num==1&&i==1) return 1;
 9     if(num==1&&i==3||num==2) return 2;
10     return 0;
11 }
12 ll dfs(ll pos,ll num,ll mod,bool limit)
13 {
14     if(!limit&&dp[pos][num][mod]!=-1) return dp[pos][num][mod];
15     if(pos==0) return num==2&&mod==0;
16     ll up=limit?a[pos]:9;
17     ll res=0;
18     for(ll i=0; i<=up; i++)
19     {
20         res+=dfs(pos-1,check(num,i),(mod*10+i)%13,limit&&i==a[pos]);
21     }
22     if(!limit) dp[pos][num][mod]=res;
23     return res;
24 }
25 ll solve(ll x)
26 {
27     ll pos=0;
28     while(x)
29     {
30         a[++pos]=x%10;
31         x/=10;
32     }
33     return dfs(pos,0,0,1);
34 }
35 int main()
36 {
37     memset(dp,-1,sizeof(dp));
38     ll a,t;
39     while(scanf("%lld",&a)!=EOF)
40     {
41         printf("%lld
",solve(a));
42     }
43     return 0;
44 }