题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3555
直接算含49的个数，还不用总想着区间
#include<cstdio>
using namespace std;
typedef long long ll;
const int LEN = 20;
__int64 dp[LEN][10], digit[LEN];
void init() {for (int j = 0; j < 10; j++)dp[1][j] = 0;for (int i = 2; i <= LEN; i++) {for (int j = 0; j < 10; j++) {for (int k = 0; k < 10; k++) {if (j == 4 && k == 9) {__int64 t = 1;for (int e = 1; e <= i - 2; e++)t *= 10;dp[i][j] += t;continue;}dp[i][j] += dp[i - 1][k];}}}
}
__int64 solve(int len) {__int64 ans = 0;digit[len + 1] = 0;for (int i = len; i >= 1; i--) {for (int j = 0; j < digit[i]; j++)ans += dp[i][j];if (digit[i + 1] == 4 && digit[i] == 9) {__int64 tmp = 0;for (int e = i - 1; e >= 1; e--)tmp = tmp * 10 + digit[e];ans += tmp + 1;break;}}return ans;
}
ll T, N;
int main(void) {init();scanf("%I64d", &T);while (T--) {scanf("%I64d", &N);int len = 0;while (N) {digit[++len] = N % 10;N /= 10;}printf("%I64d\n", solve(len));}return 0;
}