HDU 3652 B-number （数位DP，入门）

题意：

　　如果一个整数能被13整除，且其含有子串13的，称为"B数"，问[1,n]中有多少个B数？

思路：

　　这题不要用那个DFS的模板估计很快秒了。

　　状态设计为dp[位数][前缀][模13][是否含13]，前缀这一维还是有必要的（由于只有前缀1和其他不同，所以也可以用01来表示是否前缀为1）。递归出口是：出现"13"且mod=0。

 #include <bits/stdc++.h>

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <map>

 #include <algorithm>

 #include <vector>

 #include <iostream>

 #define pii pair<int,int>

 #define INF 0x7f3f3f3f

 #define LL long long

 #define ULL unsigned long long

 using namespace std;

 const double PI  = acos(-1.0);

 const int N=;

 int f[N][N][][], bit[N];

 //[位数][前缀][模13的余数][是否包含13]

 int dfs(int i,int pre,int mod,bool B,bool e)

 {

     if(i==)    return !mod&&B;

     if(!e && ~f[i][pre][mod][B])    return f[i][pre][mod][B];

     int ans=, m=;

     int u= e? bit[i]: ;

     for(int d=; d<=u; d++)

     {

         m=(mod*+d)%;

         if( pre==&&d== )

             ans+=dfs(i-, d, m, true, e&&d==u);

         else

             ans+=dfs(i-, d, m, B, e&&d==u);

     }

     return e? ans: f[i][pre][mod][B]=ans;

 }

 int cal(int n)

 {

     int len=;

     while(n)    //拆数

     {

         bit[++len]=n%;

         n/=;

     }

     return dfs(len, , , false, true);

 }

 int main()

 {

     //freopen("input.txt","r",stdin);

     memset(f,-,sizeof(f));

     int n;

     while( ~scanf("%d",&n) )

         printf("%d\n",cal(n) );

     return ;

 }

AC代码