Description

题意就是找0到N有多少个数中含有49。

\(1\leq N \leq2^{63}-1\)

Solution

数位DP，与hdu3652类似

\(F[i][state]\)表示位数为i,包含49状态为state时的方案数

注意开\(long long\)

Tips

注意N范围很大，位数不止10位！！

Code

#include <cstdio>

#include <cstring>

#define ll long long

int d[20];

ll dp[20][3],n,T;

inline ll read(){

	ll x=0,f=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

	return x*f;

}

ll dfs(int p,int sta,int lim){

	ll &tmp=dp[p][sta],r=0;

	if(!lim&&tmp!=-1) return tmp;

	if(!p) return sta==2;

	int mx=lim?d[p]:9;

	for(int i=0;i<=mx;++i){

		int t=0;

		if(sta==2) t=2;

		else if(sta==1&&i==9) t=2;

		else if(i==4) t=1;

		r+=dfs(p-1,t,lim&&(i==mx));

	}

	return lim?r:tmp=r;

}

int main(){

	T=read();

	memset(dp,-1,sizeof(dp));

	while(T--){

		n=read();

		int len=0;

		while(n){

			d[++len]=n%10;

			n/=10;

		}

		d[len+1]=0;

		printf("%lld\n",dfs(len,0,1));

	}

	return 0;

}