题意，问1~n 有多少个数含有49.
f[i][0]表示小于等于i位的不含有49数有几个。
f[i][1]表示小于等于i位的含有49的数有几个。
f[i][2]表示小于等于i位的不含有49，但是最高位是9的数有几个。
f[i][0]=f[i-1][0]+f[i-1][0]*9-f[i-1][2]; 第一个f[i-1][0]表示小于i位的所有数。f[i-1][0]*9表示i-1位的数，在第i位有9种可能。也可以理解成最高位可以是0，049就是一个两位数。
f[i][1]=f[i-1][1]*10+f[i-1][2];
f[i][2]=f[i-1][0];
49,049,0049是不是重复算了？是的，是重复算了，但“重叠”是没有关系的。两位的时候49算作一次。三位的时候049算作一次，但是49这个数不算了，已被049替代。
如果n=34549,则可以把n分成几个部分,1~29999, 30000~33999, 34000~34499, 344500~344539, 344540~344548, 344549.
3* f[4][1] + 3*f[3][1] + 4*f[2][1] + 3*f[1][1] +8*f[0][1] 单独计数。
关于这个单独计数，有个tip。作一次n++，(n+1)这次单独计数就不用算了。
如果遇到n=491934，这样，某i位的前两位是49，则后i位是不含有49的也得计入。（即把0000~1933全部计数） ①
如果某i位大于4，则应该把f[i-1][2]也计入。 ②
但是①计入以后， ②就不能计入了。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
long long f[100][3];
int main()
{
int i,j,m;
f[0][0]=1;f[0][1]=0;f[0][2]=0;
for (i=1;i<20;i++)
{
f[i][0]=f[i-1][0]*10-f[i-1][2];// no 49
f[i][1]=f[i-1][1]*10+f[i-1][2];// have 49
f[i][2]=f[i-1][0]; // zuigaowei 9 & no 49
}
int t;
scanf("%d",&t);
int cas;
char a[100];
long long n;
long long ans=0;
for (cas=0;cas<t;cas++)
{
ans=0;
scanf("%I64d",&n);
int len=0;
n++;
while (n>0)
{
a[++len]=n%10+48;
n/=10;
}
a[len+1]=' ';
a[0]='0';
a[len+1]='0';
a[len+2]='0';
bool flag=false;
for (i=len;i>=1;i--)
{
ans+=(long long )(a[i]-'0')*f[i-1][1];
if (a[i+2]=='4' && a[i+1]=='9')
flag=true;
if (flag)
ans+=(long long )f[i-1][0]*(a[i]-'0');
if (!flag && a[i]>'4')
ans+=(long long )f[i-1][2];
}
printf("%I64d
",ans);
}
return 0;
}