基本的数位dp
#include#include using namespace std;#define D(x) xconst int MAX_DIGIT = 66;long long n;int f[MAX_DIGIT];long long memoize[MAX_DIGIT][2][2][2];void to_digits(long long a){ for (int i = 0; i < MAX_DIGIT; i++) { f[i] = a % 10; a /= 10; }}long long dfs(int digit, bool less, bool contain, bool four){ if (digit == -1) { return contain; } if (memoize[digit][less][contain][four] != -1) { return memoize[digit][less][contain][four]; } int limit = less ? 9 : f[digit]; long long ret = 0; for (int i = 0; i <= limit; i++) { if (four && i == 9) { ret += dfs(digit - 1, less || i < f[digit], true, false); continue; } if (i == 4) { ret += dfs(digit - 1, less || i < f[digit], contain, true); continue; } ret += dfs(digit - 1, less || i < f[digit], contain, false); } memoize[digit][less][contain][four] = ret; return ret;}int main(){ int t; scanf("%d", &t); while (t--) { scanf("%I64d", &n); to_digits(n); memset(memoize, -1, sizeof(memoize)); long long ans = dfs(64, false, false, false); printf("%I64d\n", ans); } return 0;}