题意

给定整数 $ n $ ，求存在多少个 $ 1 $ 到 $ n $的排列 $ A $ ，使 $ \gcd ( 1 \times A_1 , 2 \times A_2 , … n \times A_n ) $

题目思路

显然，这是一道数学题，但是不会想正解也不怕（主要是我不会推正解），这种只输入一个数字的一般都是找规律题，因此我们只要打个长度较小的表就可以尝试着找规律了。

打完表后即可发现当数列的长度 $ n $ 为单数时，是没有答案的。当数列的长度 $ n $ 为偶数时，答案的数字都是某个数的平方。

打表结果如下

$ 0 \ 1 \ 0 \ 4 \ 0 \ 36 \ 0 \ 576 \ 0 \ 14400 $

可以发现，答案分别是 $ 1 , 2 , 6 , 24 , 120 $ 的平方。

我们此时再针对这串 $ 1 , 2 , 6 , 24 , 120 $ 数字进行找规律，发现每一个数与前一个数的成倍数关系，并且倍数依次加 $ 1 $ 。所以，紧接着我们就可以按照找到的规律写了。

之后发现样例的最下面有一个大样例，把样例输进去，对照一下输出，发现是正确的。因此直接开冲。

这里就放一下打表的代码好了。

void dabiao(){
    n=10;
        for(int i=1;i<=n;i++){
            a[i]=i;
        }
        for(int i=1;i<=n;i++){
            int ans=0;
            while(next_permutation(a+1,a+1+i)){
                int res=a[1];
                for(int j=2;j<=i;j++){
                    res=gcd(res,a[j]*j);
                }
                if(res>1) ans=(ans+1)%998244353;
            }
            printf("%d\n",ans);
    }
}