HDU3652：B-number——题解

http://acm.hdu.edu.cn/showproblem.php?pid=3652

题目大意：给一个数n，求1～n所有满足下列条件的数的个数：

1.包含一个子串为“13”

2.能被13整除。

————————————————————

数位dp……然而不像各位大佬记忆化搜索的写法那样清真。

欢迎访问旁边友链的学姐来获取这个我抄的代码

设dp[i][j][k][0/1][0/1]表示第i位填j，现在该数被13除余数为k，无/有“13”，前i位小于等于/大于n的前i位。

然后推的方程……太长了，看代码吧。

虽然很长但是好理解不是吗……

#include<cstdio>
#include<cstring>
using namespace std;
int a[11],b[11],f[11][10][14][2][2];
int dp(int x){
    int len=0;
    while(x)a[++len]=x%10,x/=10;
    if(len==0)a[++len]=0;
    memset(f,0,sizeof(f));
    for(int i=0;i<=9;i++){
    if(i<=a[1])f[1][i][i][0][0]=1;
    else f[1][i][i][0][1]=1;
    }
    for(int i=2;i<=len;i++){
    for(int j=0;j<=9;j++){
        for(int k=0;k<=9;k++){
        for(int l=0;l<13;l++){
            bool t=0;
            if(j==1&&k==3)t=1;
            if(j<a[i])
            if(t)
                f[i][j][(l+j*b[i-1])%13][t][0]+=f[i-1][k][l][1][0]+f[i-1][k][l][1][1]
                +f[i-1][k][l][0][1]+f[i-1][k][l][0][0];
            else{
                f[i][j][(l+j*b[i-1])%13][0][0]+=f[i-1][k][l][0][1]+f[i-1][k][l][0][0];
                f[i][j][(l+j*b[i-1])%13][1][0]+=f[i-1][k][l][1][0]+f[i-1][k][l][1][1];
            }
            else if(j==a[i])
            if(t){
                f[i][j][(l+j*b[i-1])%13][t][0]+=f[i-1][k][l][1][0]+f[i-1][k][l][0][0];
                f[i][j][(l+j*b[i-1])%13][t][1]+=f[i-1][k][l][1][1]+f[i-1][k][l][0][1];
            }
            else{
                f[i][j][(l+j*b[i-1])%13][1][1]+=f[i-1][k][l][1][1];
                f[i][j][(l+j*b[i-1])%13][1][0]+=f[i-1][k][l][1][0];
                f[i][j][(l+j*b[i-1])%13][0][1]+=f[i-1][k][l][0][1];
                f[i][j][(l+j*b[i-1])%13][0][0]+=f[i-1][k][l][0][0];
            }
            else
            if(t)
                f[i][j][(l+j*b[i-1])%13][t][1]+=f[i-1][k][l][1][0]+f[i-1][k][l][1][1]
                +f[i-1][k][l][0][1]+f[i-1][k][l][0][0];
            else{
                f[i][j][(l+j*b[i-1])%13][0][1]+=f[i-1][k][l][0][1]+f[i-1][k][l][0][0];
                f[i][j][(l+j*b[i-1])%13][1][1]+=f[i-1][k][l][1][0]+f[i-1][k][l][1][1];
            }
        }
        }
    }
    }
    int ans=0;
    for(int i=1;i<=a[len];i++)ans+=f[len][i][0][1][0];
    for(int i=len-1;i;i--){
    for(int j=1;j<=9;j++){
        ans+=f[i][j][0][1][0]+f[i][j][0][1][1];
    }
    }
    return ans;
}
int main(){
    b[0]=1;
    for(int i=1;i<=10;i++)b[i]=b[i-1]*10%13;
    int n;
    while(scanf("%d",&n)!=EOF&&n){
    printf("%d
",dp(n));
    }
    return 0;
}