A - B-number
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
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 数位dp
//2016.8.7
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string> using namespace std; int dp[][][][];
//dp[i][j][k][p]表示方法数,i表示已处理的长度，j表示mod13的余数，k表示前缀是否相同(0为相同，1为不同),p为1表示前一个数为1,为2表示已出现13，否则为0
int mi[]; int cal(int x, int n, int p)
{
return x*mi[n]%p;
} int judge(int x)//三态函数
{
if(x==)return ;
else if(x==)return ;
else return ;
} int solve(string s)
{
memset(dp, , sizeof(dp));
dp[][][][] = ;
int len = s.size();
for(int i = ; i < len; i++)
for(int j = ; j < ; j++)
for(int k = ; k < ; k++)
for(int p = ; p < ; p++)
{
if(dp[i][j][k][p]!=)
{
int l, r;
l = ; r = (k==?s[i]-'':);
for(int x = l; x <= r; x++)
{
if(p==)
dp[i+][(j+cal(x, len-i-, ))%][(k==&&x==r)?:][x==?:]+=dp[i][j][k][p];
else if(p==)
dp[i+][(j+cal(x, len-i-, ))%][(k==&&x==r)?:][judge(x)]+=dp[i][j][k][p];
else if(p==)
dp[i+][(j+cal(x, len-i-, ))%][(k==&&x==r)?:][]+=dp[i][j][k][p];
}
}
}
return dp[len][][][] + dp[len][][][];
} int main()
{
string n;
while(cin>>n)
{
mi[] = ;
for(int i = ; i < ; i++)
mi[i] = mi[i-]*%;
int ans;
ans = solve(n);
cout<<ans<<endl;
} return ;
}