思路：
dp[i][0]:没有49出现的个数
dp[i][1]:出现只4的个数
dp[i][2]:出现49的个数
代码如下：
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define ll __int64 5 using namespace std; 6 int bit[20]; 7 ll dp[20][3]; 8 ll dfs(int pos,int h,bool f) 9 { 10 if(pos==-1) return h==2; 11 if(!f&&dp[pos][h]!=-1) return dp[pos][h]; 12 ll ans=0; 13 int e=f?bit[pos]:9; 14 for(int i=0;i<=e;i++){ 15 int ha=h; 16 if(h==1&&i==9) ha=2; 17 if(h==1&&i!=9) ha=0; 18 if(h!=2&&i==4) ha=1; 19 ans+=dfs(pos-1,ha,f&&(i==bit[pos])); 20 } 21 if(!f) dp[pos][h]=ans; 22 return ans; 23 } 24 ll cal(ll n) 25 { 26 int m=0; 27 while(n){ 28 bit[m++]=n%10; 29 n/=10; 30 } 31 return dfs(m-1,0,1); 32 } 33 int main() 34 { 35 ll n; 36 int t; 37 memset(dp,-1,sizeof(dp)); 38 scanf("%d",&t); 39 while(t--){ 40 scanf("%I64d",&n); 41 printf("%I64d ",cal(n)); 42 } 43 }