## HDU 3555 Bomb

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?

### Analysis #1

#### DP 构造

F[i][j]：最高位为 j 的 i 位数字中不包含 49 的数字数量。

$$F(i,j) = \sum_{k\in [0,9]}^{k \not = 9 \text{或} j \not = 4} F(i-1,k)$$

inline void make_dp(){
for (int i=0;i<=9;i++) f[1][i]=1;
for (int i=2;i<=22;i++)
for (int j=0;j<=9;j++)
for (int k=0;k<=9;k++){
if (j==4&&k==9) continue;
f[i][j]+=f[i-1][k];
}
}

#### 答案累计

inline int calculate(int x){
int ret=0;
for (int i=a[0];i>=1;i--){
for (int j=0;j<a[i];j++) ret+=f[i][j];
if (a[i]==9&&a[i+1]==4) break;
}
return ret;
}

#### 代码

/*
* Vjudge CONTEST257056 数位DP专题练习
* B - Bomb
* 180927 By SkyWT
*/

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>

using namespace std;

#define memset_clear(_) memset(_,0,sizeof(_))
#define memset_clear_tre(_) memset(_,1,sizeof(_))
#define memset_clear_reg(_) memset(_,-1,sizeof(_))
#define memset_clear_max(_) memset(_,0x3f,sizeof(_))
#define memset_clear_min(_) memset(_,0x80,sizeof(_))
#define sqr(_) ((_)*(_))

#define write(_) cout<<#_<<" = "<<_<<endl
#define write_2(_,__) cout<<#_<<" = "<<_<<" , "<<#__<<" = "<<__<<endl
#define write_3(_,__,___) cout<<#_<<" = "<<_<<" , "<<#__<<" = "<<__<<" , "<<#___<<" = "<<___<<endl

#define int long long

int ret=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
return ret*f;
}

int T,n;
int f[25][11],a[25];

inline void make_dp(){
for (int i=0;i<=9;i++) f[1][i]=1;
for (int i=2;i<=22;i++)
for (int j=0;j<=9;j++)
for (int k=0;k<=9;k++){
if (j==4&&k==9) continue;
f[i][j]+=f[i-1][k];
}
}

memset_clear(a);
while (x) a[++a[0]]=x%10,x/=10;
}

inline int calculate(int x){
int ret=0;
for (int i=a[0];i>=1;i--){
for (int j=0;j<a[i];j++) ret+=f[i][j];
if (a[i]==9&&a[i+1]==4) break;
}
return ret;
}

signed main(){
make_dp();
while (T--){
printf("%lld\n",n+1-calculate(n+1));
}
return 0;
}

### Analysis #2

#### DP 构造

• F[i][0]：数字长度为 i，首位为任意数字，不包含 49 的数字数量
• F[i][1]：数字长度为 i，首位为 9，不包含 49 的数字数量
• F[i][2]：数字长度为 i，包含 49 的数量

$$F(i,0)=F(i-1,0)\ast 10-F(i-1,1)$$

（很好理解，要减去出现了 49 的情况）

$$F(i,1)=F(i-1,0)$$

$$F(i,2)=F(i-1,2)\ast 10+F(i-1,1)$$

（要加上这位为 4、后一位为 9 的情况）

### Analysis #3

#### 代码

#include<cstdio>
#include<cstring>
using namespace std;
#define ll long long
const int N = 100 + 5;

ll f[N][N];
int digit[N];

ll dfs(int pos, int flag, int limit) {
if (pos <= 0) return 1;
if (! limit && f[pos][flag] != -1) return f[pos][flag];
int up = limit ? digit[pos] : 9; ll cur = 0;

for (int i = 0; i <= up; ++ i) {
if (flag == 1 && i == 9) continue;
cur += dfs(pos - 1, i == 4, limit && i == up);
}
return limit ? cur : f[pos][flag] = cur;
}

ll Solve(ll x) {
memset(digit, 0, sizeof(digit)); int len = 0;
for (; x; x /= 10) digit[++ len] = x % 10;
return dfs(len, 0, 1);
}

int main(void) {
memset(f, -1, sizeof(f));
int T; scanf("%d", &T);
while (T --) {
ll r; scanf("%lld", &r);
printf("%lld\n", r + 1 - Solve(r));
}
return 0;
}