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.
数位DP，由于计算数位短点导致WA了好几次。2333
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
using namespace std;
LL bin[30],a[30],len,mod,n;
LL f[20][40][20][10],ans;
int main()
{
bin[0]=1;
for(int i=1;i<=12;i++) bin[i]=(bin[i-1]*10);
for(int i=0;i<=12;i++) f[1][i][i][0]=1;
for(int i=2;i<=12;i++)
{
for(int j=0;j<13;j++)
{
for(int k=0;k<10;k++)
{
int t=(j-k*(bin[i-1]%13)%13+13)%13;
for(int cnt=0;cnt<10;cnt++)
{
f[i][j][k][0]+=f[i-1][t][cnt][0];
f[i][j][k][1]+=f[i-1][t][cnt][1];
}
if(k==1)
{
f[i][j][k][0]-=f[i-1][t][3][0];
f[i][j][k][1]+=f[i-1][t][3][0];
}
}
}
}
while(~scanf("%lld",&n))
{
len=0;n++;mod=0;ans=0;bool flag=0;
while(n) a[++len]=n%10,n/=10;
a[len+1]=0;
for(int i=len;i>0;i--)
{
for(int j=0;j<a[i];j++)
{
ans+=f[i][mod][j][1];
if(flag||(a[i+1]==1&&j==3)) ans+=f[i][mod][j][0];
}
if(a[i+1]==1&&a[i]==3)flag=1;
mod=(mod-a[i]*(bin[i-1]%13)%13+13)%13;
}
printf("%lld\n",ans);
}
return 0;
}数位DP好像写的顺手了一点，没事时可以研究一下记忆化搜索2333