Bomb HDU - 3555
The counter-terrorists found a time bomb in the dust. But this time the terrorists improve on the time bomb. The number sequence of the time bomb counts from 1 to N. If the current number sequence includes the sub-sequence “49”, the power of the blast would add one point.
Now the counter-terrorist knows the number N. They want to know the final points of the power. Can you help them?
Input
The first line of input consists of an integer T (1 <= T <= 10000), indicating the number of test cases. For each test case, there will be an integer N (1 <= N <= 2^63-1) as the description.

The input terminates by end of file marker.
Output
For each test case, output an integer indicating the final points of the power.
Sample Input
3
1
50
500
Sample Output
0
1
15

Hint
From 1 to 500, the numbers that include the sub-sequence “49” are “49”,“149”,“249”,“349”,“449”,“490”,“491”,“492”,“493”,“494”,“495”,“496”,“497”,“498”,“499”,
so the answer is 15.

題目大意：
已知所有含有49的數字是不合法的，問$n$以內有多少不合法的數字。

解題思路：
假設$dp[i][j]$代表第$i$以下所有合法的數字的數目，$j$代表當前位是否是4.
因此，我們可以先將數字按位拆分放在數組中，從最高位開始，我們可以知道，如果當前位不為4，那么此時的$dp[i][0]$就會等于其下一位的所有情況的累加，而這種累加我們將其存在$dp[i?1][0]$與$dp[i?1][1]$中，只要算過一次，當下一次遇到時就可直接調用，大大降低了重復計算次數，當當前為為4時，將其存入$dp[i][1]$中，遍歷下一位時僅需跳過9即可，其他情況相同。

代碼：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <set>
#include <utility>
#include <sstream>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define lep(i,l,r) for(int i=l;i>=r;i--)
#define ms(arr) memset(arr,0,sizeof(arr))
//priority_queue<int,vector<int> ,greater<int> >q;
const int maxn = (int)1e5 + 5;
const ll mod = 1e9+7;
ll dp[25][2];
ll num[25];
int cnt;
ll dfs(int wei,bool limit,bool is4) {if(wei==0) return 1;if(!limit&&dp[wei][is4]) return dp[wei][is4];int maxnum;if(limit) maxnum=num[wei];else maxnum=9;ll nape=0;for(int i=0;i<=maxnum;i++) {if(is4&&i==9) continue;nape+=dfs(wei-1,limit&&i==maxnum,i==4);}if(!limit) dp[wei][is4]=nape;return nape;
}
int main() 
{#ifndef ONLINE_JUDGE//freopen("in.txt", "r", stdin);#endif//freopen("out.txt", "w", stdout);//ios::sync_with_stdio(0),cin.tie(0);int T;scanf("%d",&T);while(T--) {ll n,n1;cnt=0;scanf("%lld",&n);n1=n;while(n) {num[++cnt]=n%10;n=n/10;}printf("%lld\n",n1+1-dfs(cnt,true,false));}return 0;
}