?
大致题意：B-number即一个整数含有子串13且被13整除。求1-n之间这样的数的个数。
思路：有两个限制条件：含有子串“13”和能被13整除。那么设dp[site][mod][flag]，表示到第site位对13取余为mod且标记为flag的数的个数。flag表示是否含有子串13。然后进行记忆话搜索。
#include #include #include #include #include #include #include #include #include #include #include #define LL long long #define _LL __int64 #define eps 1e-8 #define PI acos(-1.0) using namespace std; int dp[15][15][5]; int dig[15]; //flag = 0表示前一个不是1，flag = 1表示前一个是1，flag = 2表示出现13。 int dfs(int site, int mod, int flag, int up) { if(site == 0) return mod == 0 && flag == 2; //当mod为0且有13时，返回1 if(!up && dp[site][mod][flag] != -1)//记忆化 return dp[site][mod][flag]; int len = up ? dig[site] : 9; int ans = 0; for(int i = 0; i <= len; i++) { int tmod = (mod*10 + i) % 13; int tflag = flag; if(flag == 1 && i == 3) tflag = 2; else if(flag == 0 && i == 1) tflag = 1; else if(flag == 1 && i != 1) tflag = 0; ans += dfs(site-1, tmod, tflag, up && (i == len) ); } if(!up) dp[site][mod][flag] = ans; return ans; } int cal(int n) { int cnt = 0; while(n) { dig[++cnt] = n % 10; n /= 10; } memset(dp,-1,sizeof(dp)); return dfs(cnt,0,0,1); } int main() { int n; while(~scanf(%d,&n)) { printf(%d ,cal(n)); } return 0; }