代码语言：javascript复制
//hdoj 3555
//2013-06-27-16.53
#include <stdio.h>
#include <string.h>
__int64 dp[21][3], n;
int len, bit[21];
//dp[i][0] 长度为i 包含49的个数
//dp[i][1] 长度为i没有49但以9开头的
//dp[i][2] 长度为i 没有49
void init()
{
dp[0][2] = 1;
for (int i = 1; i < 20; i )
{
dp[i][0] = (__int64)dp[i-1][0]*10 dp[i-1][1];
dp[i][1] = dp[i-1][2];
dp[i][2] = (__int64) dp[i-1][2]*10 - dp[i-1][1];
}
}
int main()
{
init();
int t;
scanf("%d", &t);
while (t--)
{
scanf("%I64d", &n);
len = 0;
n ;
while (n)
{
bit[ len] = n;
n /= 10;
}
bit[len 1] = 0;
__int64 ans = 0;
bool flag = false;
for (int i = len; i; i--)
{
ans = (__int64)dp[i-1][0]*bit[i];
if (flag)
ans = dp[i-1][2]*bit[i];
if (!flag && bit[i] > 4)
ans = dp[i-1][1];
if (bit[i] == 9 && bit[i 1] == 4)
flag = true;
}
printf("%I64dn", ans);
}
return 0;
}
