学步园

dp[][0]表示不包含49并且以非4结尾的个数

dp[][1]表示不包含49并且以4结尾的个数

dp[][2]表示包含49的个数

所以转移方程是：

dp[k][0]=dp[k-1][0]*9+dp[k-1][1]*8;
dp[k][1]=dp[k-1][0]+dp[k-1][1];

dp[k][2]=dp[k-1][1]+dp[k-1][2]*10;

实现：从最高位开始，固定每一位，枚举数量。注意处理如49,549.。。之类的特殊数，要n+1

#include <list>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <deque>
#include <stack>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <limits.h>
#include <time.h>
#include <string.h>
using namespace std;

#define LL long long
#define PI acos(-1.0)
#define MAX INT_MAX
#define MIN INT_MIN
#define eps 1e-10
#define FRE freopen("a.txt","r",stdin)
#define N 25

LL dp[21][3];
int num[21];
int state(int now,int n){
    if(now==0){
        if(n==4)return 1;
        return 0;
    }
    if(now==1){
        if(n==9)return 2;
        if(n==4)return 1;
        return 0;
    }
    return 2;
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        LL n;
        scanf("%I64d",&n);
        n++;
        int i,j,k;
        int cnt=1;
        while(n){
            num[cnt++]=n%10;
            n/=10;
        }
        int len=cnt-1;
        int b=0;
        int now=0;
        LL ans=0;
        for(i=len;i>=1;i--){
            b++;
            for(j=0;j<num[i];j++){
                memset(dp,0,sizeof(dp));
                dp[b][state(now,j)]=1;
                for(k=b+1;k<=len;k++){
                    dp[k][0]=dp[k-1][0]*9+dp[k-1][1]*8;
                    dp[k][1]=dp[k-1][0]+dp[k-1][1];
                    dp[k][2]=dp[k-1][1]+dp[k-1][2]*10;
                }
                ans+=dp[len][2];
            }
            now=state(now,num[i]);
        }
        printf("%I64d\n",ans);
    }
    return 0;
}