hdu 3555 Bomb
题意:
在1~N(1<=N<=2^63-1)范围内找出含有 ‘49’的数的个数；
与hdu 2089 不要62的区别:2089是找不不含 '4'和 '62'的区间范围内的数，此题是含有；正好相反，对于 "不要62"只是用第二位表示首位数字，这一题呢？
看转化:易知一定要要知道首位是9的个数，才能在前面加4得到 '49'，但是什么状态能从不含 '49'转移到含 '49'?直接在不含'49'前加9，那么就出现了三个状态之间的递推转化，从而推出了第二维要使用三个状态来得出长度为i时的所有情况；
二维的状态：
[0]:只是不含 '49',不管首位(可以是9); [1]:不含 '49',但首位是9; [2]:含有 '49'
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(i = 0;i < (n);i++)
typedef long long ll;
ll f[][];
void init()
{
f[][] = ;
for(int i = ;i <= ;i++){
f[i][] = f[i-][] * - f[i-][];
f[i][] = f[i-][]; // start with 9
f[i][] = f[i-][] + f[i-][]*; // contian 49
}
}
ll query(ll n)
{
int d[]={},tot = ;
while(n){
d[++tot] = n % ;
n /= ;
}
ll ans = ,flag = ;
for(int i = tot;i > ;i--){
ans += f[i-][]*d[i];
if(flag && d[i] > ) ans += f[i-][];
if(!flag) ans += f[i-][]*d[i];
if(d[i+] == && d[i] == ) flag = ;
}
return ans;
}
int main()
{
init();
int T;
cin>>T;
while(T--){
ll n;
scanf("%I64d",&n);
printf("%I64d\n",query(n+));
}
}