描述

在所有的N位数中，有多少个数中有偶数个数字3？

 

输入

第一行为一个整数T，代表有T组数据。（T<10000）
接下来T行，每行一个正整数N。（1<=N<=1000）

输出

每行输出一个整数，即方案数(由于结果可能很大，你只需要输出这个答案mod 12345的值。)。

样例输入

1
2

样例输出

73

代码:

#include<stdio.h>
int odd[1001],even[1001];
int main()
{
	int i;
	odd[1]=1,even[1]=8;
	for(i=2;i<1001;++i)
	{
		odd[i]=(even[i-1]+odd[i-1]*9)%12345;
		even[i]=(even[i-1]*9+odd[i-1])%12345;
	}
	int T,n;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		printf("%d\n",even[n]%12345);
	}
	return 0;
}

NYOJ-偶数个3