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? InputThe 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. OutputFor each test case, output an integer indicating the final points of the power.Sample Input3150500Sample Output0115HintFrom 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.
题意 ：在【0，n】范围内有出现了多少次 “49”
思路：数位dp
dp[i][0] 表示 长度为 i 不出现 “49” 的个数
dp[i][1] 表示 长度为 i 最高位为 “9” 且不含“49”的个数
dp[i][2] 表示 长度为 i 出现 “49” 的个数
那么对0 ~ 2^63-1 内进行初始化
ll dp[25][3];
void init(){
dp[0][0]=1;
dp[0][1]=dp[0][2]=0;
for (int i=1;i<=20;i++){
dp[i][0]=dp[i-1][0]*10-dp[i-1][1]; /* 长度为 i 中 不包含 “49”的个数
为长度为 i-1 中不含“49”的个数在第 i 位 加 0~9 的个数 减掉 当第 i 位为“4”时，长度为 i-1
的数中最高位为“9”的个数 */
dp[i][1]=dp[i-1][0];/*长度为 i-1的数中不含“49”的数在第 i 位加“9”
即为dp[i][1];*/
dp[i][2]=dp[i-1][2]*10+dp[i-1][1];/* 长度为i的数中含“49”的个数等于长度为 i-1 中含“49” 的数字 在第 i 位上放0~9，加当第 i 位为“4”时，长度为 i-1 的数字中，最高位
为“9”的数字。*/
}
ll getCnt(ll x){
++x; /*为啥加一我也不知道，反正加一就过了 qwq */
ll ans=len=0;
while(x){
num[++len]=x%10;
x/=10;
}
bool fg=false; /* 种一个标记判断到第i位是 最高位到第i+1位 是否出现“49”*/
num[len+1]=-1;
for (int i=len;i>=1;i--){
ans+=dp[i-1][2]*num[i]; //第i位 取（0~num[i]-1）时 长度为i-1的数中含“49”的数
if(fg) ans+=dp[i-1][0]*num[i]; /*如果高位中已经出现过“49”，第i位取（0~num[i]-1）时，长度为i-1中不含“49”的个数*/
if(!fg && num[i]>4) ans+=dp[i-1][1]; /*当未标记且该位大于4时，取长度为i-1的数中最高位为“9”的数*/
if(num[i+1]==4 && num[i]==9) fg=1; /*如果该位为9前一位为4 则标记*/
}
return ans;
}过题代码如下：#include <cstdio>
#include <cstring>
#include <algorithm>
#include <functional>
#include <iostream>
using namespace std;
typedef long long ll;
ll x,len;
int num[25];
ll dp[25][3];
void init(){
dp[0][0]=1;
dp[0][1]=dp[0][2]=0;
for (int i=1;i<=20;i++){
dp[i][0]=dp[i-1][0]*10-dp[i-1][1];
dp[i][1]=dp[i-1][0];
dp[i][2]=dp[i-1][2]*10+dp[i-1][1];
}
}
ll getCnt(ll x){
++x;
ll ans=len=0;
while(x){
num[++len]=x%10;
x/=10;
}
bool fg=false;
num[len+1]=-1;
for (int i=len;i>=1;i--){
ans+=dp[i-1][2]*num[i];
if(fg) ans+=dp[i-1][0]*num[i];
if(!fg && num[i]>4) ans+=dp[i-1][1];
if(num[i+1]==4 && num[i]==9) fg=1;
}
return ans;
}
int main(){
init();
int T;
scanf("%d",&T);
while(T--){
scanf("%I64d",&x);
printf("%I64d
",getCnt(x));
}
return 0;
}