Time Limit: 2000/1000 MS ( Java/Others) ? ?Memory Limit: 131072/65536 K (Java/Others)

Total Submission(s): 7921 ? ?Accepted Submission(s): 2778

?

?

?

Problem Description

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?

?

?

?

Input

The 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.

?

?

?

Output

For each test case, output an integer indicating the final points of the power.

?

?

?

Sample Input

3 1 50 500

?

?

?

Sample Output

0 1 15

Hint

From 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.

?

?

?

Author

fatboy_cw@WHU

?

?

?

Source

2010 ACM-ICPC Multi-University Training Contest（12）——Host by WHU

?

题意： 给你一个数n,要你统计出1到n中出现含有49数字的个数： 比如 498,549,49.....

对于这一道题： 看到一个博客引用了这张图片，觉得说的很清晰，就引用了..

?

?

我们对于 i-1长度的数字分析，无疑就这么集中情况（当然只是围绕49来说的哇）首部分析：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? i-1长度 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?那么对于 i长度

首部为49 ，那么它的格式必然为： ? ? ? ? ? ? ?49**** ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ？49****（？可能为9）

?

首部保函9 ，那么它的格式必然为： ? ? ? ? ? ? 9***** ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ？9*****（？可能为4）

?

首部部位49 ，那么它的格式为： ? ? ? ? ? ? ? ?******* ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?？*******（？可能为9）

?

? ? 我们不妨用dp[i][2]表示首部为49的,dp[i][1]表示首部为9的，dp[i][0]表示首部不为49，于是我们可以发现这样一个规律：

?

? ? ?dp[i-1][2]向前移一位，即原来的个位变为十位，十位变为百位的那种移位。 形成dp[i][2],但是需要注意的是:

? ? ? 当dp[i-1][2]时，其实由我上面说的，？可能为9 ，所以当向前移一位时，？为9的可能性被去掉了。所以

? ? dp[i-1][2]*10（移动一位时）需要减去 开头为9的那种模式dp[i-1][1],所以得到：

? （1） ? ? ?dp[i][2]=dp[i-1][2]*10-dp[i-1][1];

? ? 对于i位首部为9那么后面只需要满足不为49即可，刚好满足dp[i][0];

? （2） ?所以 dp[i][1]=d[i-1][0];

? ?对于首部不为49的

? ? ? ?同样也可以分析出来...

? ? ? dp[i][0]=dp[i-1][0]*10+dp[i-1][1];

?

于是得到这样一个预处理方程：

? ? ? ? ? ? ? ? ? ? ? ? dp[i][2]=dp[i-1][2]*10-dp[i-1][1];

? ? ? ? ? ? ? ? ? ? ? ? dp[i][1]=d[i-1][0];?

? ? ? ? ? ? ? ? ? ? ? ? dp[i][0]=dp[i-1][0]*10+dp[i-1][1];

代码：详情见代码：

?1 //#define LOCAL

?2 #include

?3 #include

?4 #define LL __int64

?5 using namespace std;

?6 ?const int maxn=25;

?7 LL dp[maxn][3]={0};

?8 int nn[maxn];

?9 int main()

10 {

11?

12 ? #ifdef LOCAL

13 ? ? freopen("test.in","r",stdin);

14 ? #endif

15 ?int cas,i;

16 ?LL n;

17 ?scanf("%d",&cas);

18 ?/*数位DP的惯有模式预处理*/

19 ?dp[0][0]=1;

20 ?for(i=1;i<=20;i++)

21 ?{

22 ? ? dp[i][0]=dp[i-1][0]*10-dp[i-1][1];

23 ? ? dp[i][1]=dp[i-1][0];

24 ? ? dp[i][2]=dp[i-1][2]*10+dp[i-1][1];

25 ?}

26 ?while(cas--)

27 ?{

28 ? ?scanf("%I64d",&n);

29 ? ?i=0;

30 ? ?n+=1;

31 ? ?memset(nn,0,sizeof(nn));

32 ? ?while(n>0)

33 ? ?{

34 ? ? ?nn[++i]=n%10;

35 ? ? ?n/=10;

36 ? ?}

37 ? ?LL ans=0;

38 ? ?bool tag=0;

39 ? ?int num=0;

40 ? ?for( ?; i>=1 ?; i-- ?)

41 ? ?{

42 ? ? ? ? ?ans+=dp[i-1][2]*nn[i]; ?/*计算49开头的个数*/

43 ? ? ? ? ?if(tag){

44 ? ? ? ? ans+=dp[i-1][0]*nn[i]; ? /*当前面出现了49的时候，那么后面出现的任何数字也要进行统计*/

45 ? ? ? }

46 ? ? ? if(!tag&&nn[i]>4)

47 ? ? ? {