B-number

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1658 Accepted Submission(s): 906 Problem Description A wqb-number, or B-number for short, is a non-negative integer whose decimal form contains the sub- string "13" and can be divided by 13. For example, 130 and 2613 are wqb-numbers, but 143 and 2639 are not. Your task is to calculate how many wqb-numbers from 1 to n for a given integer n. Input Process till EOF. In each line, there is one positive integer n(1 <= n <= 1000000000). Output Print each answer in a single line. Sample Input 13 100 200 1000 Sample Output 1 1 2 2 含有数字13且能够被13整除的数的个数 #include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <cmath> #include <algorithm> #include <vector> #include <map> #include <string> #include <stack> using namespace std; typedef long long ll; #define PI 3.1415926535897932 #define E 2.718281828459045 #define INF 0x3f3f3f3f #define mod 100000007 const int M=1005; int n,m; int cnt; int sx,sy,sz; int mp[1000][1000]; int pa[M*10],rankk[M]; int head[M*6],vis[M*100]; int dis[M*100]; ll prime[M*1000]; bool isprime[M*1000]; int lowcost[M],closet[M]; char st1[5050],st2[5050]; int len[M*6]; typedef pair<int ,int> ac; //vector<int> g[M*10]; int dp[50][50][20][10]; int has[10500]; int month[13]= {0,31,59,90,120,151,181,212,243,273,304,334,0}; int dir[8][2]= {{0,1},{0,-1},{-1,0},{1,0},{1,1},{1,-1},{-1,1},{-1,-1}}; void getpri() {     ll i;     int j;     cnt=0;     memset(isprime,false,sizeof(isprime));     for(i=2; i<1000000LL; i++)     {         if(!isprime[i])prime[cnt++]=i;         for(j=0; j<cnt&&prime[j]*i<1000000LL; j++)         {             isprime[i*prime[j]]=1;             if(i%prime[j]==0)break;         }     } } struct node {     int v,w;     node(int vv,int ww)     {         v=vv;         w=ww;     } }; vector<int> g[M*100]; string str[1000]; int bit[50]; /* //dp[i][j][k][z]：i:处理的数位，j:该数对13取模以后的值，k:是否已经包含13,z结尾的数(dp[i][j]表示i为高位且i位为数字j时满足题意的种数) int dfs(int cur,int s,bool h13,int pre,int e,int z){     if(cur<0) return h13&&(s==0);//return 1;含有数字13且能够被13整除的数     if(!e&&!z&&dp[cur][s][h13][pre]!=-1) return dp[cur][s][h13][pre];//dp[cur][pre]不能变,相当于模板的dp[cur][s],因为是交事件，加两项     int endx=e?bit[cur]:9;     int ans=0;     for(int i=0;i<=endx;i++){             //if(!z&&abs(i-s)<2)continue;         if(z&&!i) ans+=dfs(cur-1,(s*10+i),h13,i,e&&i==endx,1);         else ans+=dfs(cur-1,(s*10+i),h13||(pre==1&&i==3),i,e&&i==endx,0);     }     if(!e&&!z) dp[cur][s][h13][pre]=ans;     return ans; } int dp[15][15][3],s[15];//dp[i][j][k]，i表示位数，j表示余数，k表示末尾是1、末尾不是1、含有13.   int dfs(int pos, int mod, int have, int lim)//前三个数对应数组dp，lim表示上限 {     int num,ans,mod_x,have_x;     if (pos <= 0)         return mod==0&&have==2;     if (!lim && dp[pos][mod][have]!=-1) //没有上限且被访问过         return dp[pos][mod][have];     ans = 0;     num = lim?s[pos]:9;//如果有上限，只能取到当前位数，如果没上限，可取到9                         //假设该位是2，下一位是3，如果现在算到该位为1，那么下一位是能取到9的，如果该位为2，下一位只能取到3     for (int i=0; i<=num; i++)     {         mod_x = (mod*10+i);//该位的每种情况对13取模         have_x = have;         if (have==0 && i==1)//末尾加1             have_x=1;         if (have==1 && i!=1)//末尾已经为1了             have_x=0;         if (have==1 && i==3)//末尾是1，现在加3             have_x=2;         ans+=dfs(pos-1, mod_x, have_x, lim&&i==num);//如果i==num，下一位能取的最大数就为s[pos-1]，i！=num，下一位能取到9     }     if (!lim)         dp[pos][mod][have] = ans;     return ans; }*/ //压缩版 int get(int t,int i){       if(t==2||(t==1&&i==3))return 2;  //2是含有13     if(i==1)return 1;  //当前为一，对下个状态而言，上一位就是1     return 0;  //其他数 }   int dfs(int pos,int s,int h13,int flag ){  //pre     if(cur<0)return s==0&&h13==2;       if(!flag&&dp[cur][s][h13]!=-1)return dp[cur][s][h13];       int ans=0,u=flag?pri[cur]:9;       for(int i=0;i<=u;i++){       ans+=dfs(cur-1,(s*10+i),get(h13,i),flag&&i==u);       //printf("%d %d %d\n",ans,pos,i);       }       return flag?ans:dp[cur][s][h13]=ans;   }   int solve(int n){     int len=0;     while(n){         bit[len++]=n;         n/=10;     }     return dfs(len-1,0,0,0,1,1); } int main() {     int i,j,k,t;     int l,r;     while(~scanf("%d",&r))     {         memset(dp,-1,sizeof(dp));         printf("%d\n",solve(r));     }     return 0; }