Description

题目大意：求小于n是13的倍数且含有'13'的数的个数。

(1 <= n <= 1000000000)

Solution

数位DP，题目需要包含13，且被13整除，所以状态应该多2个，

\(F[i][j][k]\)表示位数为i，余数为j，包含13状态为k的方案数

其中k(0,1,2)，2表示已经包含13，1表示上一个为1，否则为0

记忆化打法

Tips:

1. 数组k维要开到3
2. DP数组只算一次，只需开始初始化一次
3. 计算转移的k时的顺序

Code

#include 
    
     #include 
     
      int n,d[15],f[15][15][3];int dfs(int p,int mo,int exi,int lim){    int &tmp=f[p][mo][exi],r=0;    if(!p) return exi==2&&!mo;    if(!lim&&tmp!=-1) return tmp;           int mx=lim?d[p]:9;    for(int i=0;i<=mx;++i){        int t=0;        if(exi==2) t=2;//必须先判，否则错解        else if(exi==1&&i==3) t=2;        else if(i==1) t=1;        r+=dfs(p-1,(mo*10+i)%13,t,lim&&(i==mx));    }    return lim?r:tmp=r;}int main(){    memset(f,-1,sizeof(f));    while(~scanf("%d",&n)){        int len=0;        while(n){            d[++len]=n%10;            n/=10;        }        printf("%d\n",dfs(len,0,0,1));    }    return 0; }