Bomb

Bomb

思路
$dp\left[pos\right]\left[sta\right]表示表示第pos+1位（高位）是4（不是4）的个数且第pos+1位没有达到limit$dp[pos][sta]表示表示第pos+1位（高位）是4（不是4）的个数且第pos+1位没有达到limit
AC代码解释

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
ll a[65];
ll dp[65][2];
///快速求a^n
ll my_pow(ll a, ll n){
	ll sum = 1;
	while(n){
		if(n & 1) sum *= a;
		a *= a;
		n >>= 1;
	}
	return sum;
}
ll dfs(ll pos, ll pre, bool sta, bool limit){
	if(pos == 0) return 0;
	if(!limit && dp[pos][sta] != -1) return dp[pos][sta];
	///如果没有到底limit且第pos+1位的sta情况已经确定我们就直接使用
	ll up = limit ? a[pos] : 9;
	ll tmp = 0;
	for(ll i = 0; i <= up; i++){
	///如果上一位是4且这一位是9表明已经凑出第一个49，那么后面的位就不需枚举，直接数学公式计算
		if(pre == 4 && i == 9){
			if(!(limit && i == a[pos]))
				tmp += my_pow(10, pos - 1);
			///如果49不是Limit的话，我们就无需担心其他数位的取值情况
			else{
		        ll temp = 1;
				for(ll j = pos - 1; j > 0; j--){
					temp += a[j] * my_pow(10, j - 1);///考虑边界情况
				}
				tmp += temp;
			}
		}
		else tmp += dfs(pos - 1, i, i == 4, limit && i == a[pos]);
	}
	if(!limit) dp[pos][sta] = tmp;
	return tmp;
}
ll solve(ll n){
	memset(dp, -1, sizeof(dp));
	ll cnt = 0;
	while(n){
		a[++cnt] = n % 10;
		n /= 10;
	}
	///预处理n的所有位
	return dfs(cnt, -1, false, true);
}
int main(){
    int t;
    scanf("%d", &t);
    while(t--){
	ll n;
	scanf("%lld", &n);
	printf("%lld\n", solve(n));
    }
    return 0;
}