偶数个3

偶数个3

时间限制： 1000 ms | 内存限制： 65535 KB

难度： 1

描述

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

输入

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

输出

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

样例输入

1
2

样例输出

import java.util.Scanner;

public class Main {

 static int arr[] = new int[10005];
 static int temp[] = new int[10005];

 public static void main(String[] args) {
  Scanner scanner = new Scanner(System.in);
  int times = scanner.nextInt();
  while (times-- != 0) {
   int number = scanner.nextInt();
   arr[1] = 8;
   arr[2] = 73;
   temp[1] = 1;
   for (int i = 2; i <= number; i++) {
    temp[i] = (9 * temp[i - 1] + arr[i - 1]) % 12345;
   }
   for (int i = 3; i <= number; i++) {
    arr[i] = (temp[i - 1] + 9 * arr[i - 1]) % 12345;
   }
   System.out.println(arr[number]);
  }
 }

}