Cf #779 (Div. 2) - B

题目链接

题意

给一个1~n的排列，若满足以下条件则是一个“美丽排列”。

gcd(1*p1,2*p2,...,n*pn) > 1 ( gcd 求所以元素的最大公约数 )

给定一个n，问有多少种美丽排列，模998244353 。

思路

若 n 为奇数则答案为 0

为偶数则让奇偶相乘 有 (n/2)! * (n/2)!

代码

#include 
using namespace std;
int mod = 998244353;
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        long long a = 1;
        int n;
        cin >> n;
        if (n % 2 == 1)
        {
            cout << 0 << endl;
            continue;
        }
        for (int i = 1; i <= n / 2; i++)
        {
            a = a * i;
            a = a % mod;
        }
        cout << (a * a) % mod << endl;
    }
    return 0;
}