Description

题意就是找0到N有多少个数中含有49。

\(1\leq N \leq2^{63}-1\)

Solution

数位DP，与hdu3652类似

\(F[i][state]\)表示位数为i,包含49状态为state时的方案数

注意开\(long long\)

Tips

注意N范围很大，位数不止10位！！

Code

#include 
    
     #include 
     
      #define ll long longint d[20];ll dp[20][3],n,T;inline ll read(){    ll x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}    return x*f;}ll dfs(int p,int sta,int lim){    ll &tmp=dp[p][sta],r=0;    if(!lim&&tmp!=-1) return tmp;    if(!p) return sta==2;        int mx=lim?d[p]:9;    for(int i=0;i<=mx;++i){        int t=0;        if(sta==2) t=2;        else if(sta==1&&i==9) t=2;        else if(i==4) t=1;        r+=dfs(p-1,t,lim&&(i==mx));    }    return lim?r:tmp=r;}int main(){    T=read();    memset(dp,-1,sizeof(dp));    while(T--){        n=read();        int len=0;        while(n){            d[++len]=n%10;            n/=10;         }        d[len+1]=0;        printf("%lld\n",dfs(len,0,1));    }    return 0;}