hdu 3652 B-number

http://acm.hdu.edu.cn/showproblem.php?pid=3652

数位dp

题意：求1到n中能被13整除且含有13的数的个数。dp[i][j][k][c]表示dfs到i位，余数为j，是否含有13的标志k，最后一个数为m的有多少个符合要求的数。

dfs枚举每一位。

 1 #include <cstdio>
 2 #include <cstring>
 3 #define ll int
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 ll n;
 8 ll dp[15][15][10][15];
 9 int num[30];
10 
11 ll dfs(int pos,int c,bool x,int m,bool flag)
12 {
13     if(pos==-1) return (x&&c==0);
14     if(!flag&&dp[pos][c][x][m]!=-1) return dp[pos][c][x][m];
15     ll ans=0;
16     int xx=flag?num[pos]:9;
17     for(int i=0; i<=xx; i++)
18     {
19         ans+=dfs(pos-1,(c*10+i)%13,x||(m==1&&i==3),i,flag&&(i==xx));
20     }
21     if(!flag) dp[pos][c][x][m]=ans;
22     return ans;
23 }
24 
25 
26 int main()
27 {
28     memset(dp,-1,sizeof(dp));
29     while(scanf("%d",&n)!=EOF)
30     {
31         int cnt=0;
32         while(n)
33         {
34             num[cnt++]=n%10;
35             n=n/10;
36         }
37         printf("%d
",dfs(cnt-1,0,false,0,true));
38     }
39     return 0;
40 }

View Code