(题目链接)

题意

　　求区间${[1,n]}$含有49的数的个数。

Solution

　　数位dp，先求出不含49的，再减一下就好了。

细节

　　LL

代码

// hdu3555#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define LL long long#define inf (1ll<<30)#define MOD 1004535809#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;LL f[20][10],g[20],m,ans;int t[20],n;int main() { int T;scanf("%d",&T); while (T--) { scanf("%lld",&m);ans=m; for (n=0;m;m/=10) t[++n]=m%10; memset(f,0,sizeof(f));memset(g,0,sizeof(g)); g[1]=1; for (int i=0;i<10;i++) f[1][i]=1; for (int i=2;i<=n;i++) { for (int j=0;j<10;j++) for (int k=0;k<10;k++) if (j!=4 || k!=9) f[i][j]+=f[i-1][k]; for (int j=0;j