/*
dp[i][0|1|2]:没有49的个数|最高位是9，没有49的个数|有49的个数
dp[i][0]=10*dp[i-1][0]-dp[i-1][1]
dp[i][1]=dp[i-1][0]
dp[i][2]=10*dp[i-1][2]+dp[i-1][1]
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll dp[30][
4],n,t;
void init(){
dp[0][
0]=
1;
for(
int i=
1;i<=
29;i++
){
dp[i][0]=
10*dp[i-
1][
0]-dp[i-
1][
1];
dp[i][1]=dp[i-
1][
0];
dp[i][2]=
10*dp[i-
1][
2]+dp[i-
1][
1];
}
}
/*
49149249349449
*/
ll query(ll n){
ll tmp=n+
1,res=
0;
ll flag=
0,m=
0,a[
29]=
{};
while(tmp)a[++m]=tmp%
10,tmp/=
10;
for(
int i=m;i>=
1;i--
){
for(
int j=
0;j<a[i];j++
){
res+=dp[i-
1][
2];
if(flag)res+=dp[i-
1][
0];
}
//处理余下的部分
if(!flag && a[i]>
4)res+=dp[i-
1][
1];
if(a[i+
1]==
4&&a[i]==
9)flag=
1;
}
return res;
}
int main(){
init();
cin>>
t;
while(t--
){
cin>>
n;
cout<<query(n)<<
endl;
}
}
转载于:https://www.cnblogs.com/zsben991126/p/10682854.html
