B-number

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 6128    Accepted Submission(s): 3528 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   Author wqb0039   Source 2010 Asia Regional Chengdu Site —— Online Contest

题意是求1~n里有多少个数，数位上有13存在且这个数取余13==0

数位dp

state：1,：前一位是1    2：前面有13出现    否则0

当时不知道怎么满足取余13等于0，其实按位数的权值一位一位的加，并膜13，只保留余数即可

这样：dp【位数】【state】【余数】

核心是想到记录余数这个状态，只有前面的余数相同，后面能取的个数才和之前求并记忆的一样

#include<stdio.h> #include<string.h> #include<math.h> #include<string> #include<algorithm> #include<queue> #include<vector> #include<map> #include<set> #define eps 1e-9 #define PI 3.141592653589793 #define bs 1000000007 #define bsize 256 #define MEM(a) memset(a,0,sizeof(a)) #include<iostream> typedef long long ll; using namespace std; int dp[100][3][15]; int a[100]; int dfs(int pos,int state,int limit,int yu,long long t) { if(pos==-1) { return state==2&&yu==0; } if(!limit&&dp[pos][state][yu]!=-1) return dp[pos][state][yu]; int up=limit?a[pos]:9; int ans=0; int now; for(int i=0;i<=up;i++) { if(state==2) now=2; else if(state==1&&i==3) now=2; else if(i==1) now=1; else now=0; ans+=dfs(pos-1,now,limit&&i==a[pos],(yu+i*t),t/10); } if(!limit&&dp[pos][state][yu]==-1) { dp[pos][state][yu]=ans; } return ans; } int solve(int x) { int pos=0; long long t=1; while(x) { a[pos++]=x; x/=10; t*=10; } return dfs(pos-1,0,1,0,t/10); } int main() { int n; memset(dp,-1,sizeof(dp)); while(~scanf("%d",&n)) { printf("%d\n",solve(n)); } return 0; }