[Codeforces Round #779 (Div. 2)] B. Marin and Anti-coprime Permutation

 

---

※ 1과 2를 항상 포함하기 때문에 1은 무조건 2번째 자리 이상에 가야한다.

※ 홀수는 무조건 짝수 번 째 자리에 와야 한다. (훌수 * 홀수 = 홀수, 홀수 * 짝수 = 짝수)

※ n이 홀수라면 홀수가 무조건 홀수 자리에 들어갈 수 밖에 없어 최대공약수가 존재하지 않는다.

 

1. n이 짝수 일 때 홀수의 수 = n/2 순서를 고려하여 n/2 개의 홀수를 뽑는 경우의 수 (n/2) !

2. 짝수의 수 = n/2 경우의 수 (n/2)!

3. (n/2)! * 2 % 998244353

4. 998244353을 넘어가면 %998244353을 해준다(마지막 결과에도 적용해줘야함 998244353을 넘어갈 수 있음)

 

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Main {
	static long[] dp;
 	public static void main(String arg[]) throws IOException {
 		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 		int T = Integer.parseInt(br.readLine());
 		dp = new long[501];
 		dp[0] = 0;
 		dp[1] = 1;
 		while(T --> 0) {
 			int n = Integer.parseInt(br.readLine());
 			long gcd = fac(n/2);
 			if(n%2 == 0)
 			System.out.println((gcd * gcd) % 998244353);
 			else
 				System.out.println(0);
 		}
 	}
 	static long fac(int n) {
 		if(n <= 1)
 			return n;
 		if(dp[n] != 0)
 			return dp[n];
 		return dp[n] = (n * fac(n-1)) % 998244353;
 	}
}