Problem Description
在所有的N位数中，有多少个数中有偶数个数字3？由于结果可能很大，你只需要输出这个答案对12345取余的值。
Input
输入一个数N(1<=N<=1000)，输入以0结束。
Output
对于每一个N输出有多少个数中有偶数个数字3。
Sample Input
2 0
Sample Output
73 【样例说明】 在所有的2位数字，包含0个3的数有72个，包含2个3的数有1个，共73个
规律：在 1 位数字中：很容易得到，包含3为偶数个的数有 8 个，奇数个的数有 1 个；
在 2 位数中：先不看十位：个位是 0~9 ；那么除了出现 3，基本上就是和在 1 位数的时候是一样的；
偶数个：10 - 19 9个； 20 - 29 9个； 30 - 39 1个； 40 - 49 9个；……90 - 99 9个；
奇数个：10 - 19 1个； 20 - 29 1个； 30 - 39 9个； 40 - 49 1个；……90 - 99 1个；
在 2 位数中：包含3为偶数个的数有 9*8+1； 奇数个有 1*8+9=1*9+8；
# include<stdio.h>
int main()
{
int dp[1001][2],i;
dp[1][0]=1; dp[1][1]=8;
for(i=2;i<=1000;i++)
{
dp[i][0]=(dp[i-1][1]+dp[i-1][0]*9)%12345;
dp[i][1]=(dp[i-1][1]*9+dp[i-1][0])%12345;
}
int n;
while(~scanf("%d",&n)&&n)
{
printf("%d\n",dp[n][1]);
}
return 0;
}