出题人题解 | #筱玛的排列#

原题解链接：https://ac.nowcoder.com/discuss/151505

显然$n\mathrm{\ne }1n\ne 1$且$nmod4\mathrm{\ne }0n\; \backslash ,mod\backslash ,\; 4\; \ne \; 0$时答案为$00$, $n=1n=1$答案为$11$。

下面考虑 $nmod4=0n\; \backslash ,mod\; \backslash ,4\; =\; 0$的情况：

假设 $a_t=ta\_\{t\}=t$, 取 $i=j=ti=\; j=t$ 有 $2t=n+12\; t=n+1$ 。

这时$nn$是奇数,矛盾。

若 $a_t=n+1-ta\_\{t\}=n+1-t$, 取 $i=n+1-t,j=ti=n+1-t,\; j=t$, 同样矛盾。

假设 $a_t=u(u\mathrm{\ne }t,u\mathrm{\ne }n+1-t)a\_\{t\}=u(u\; \backslash neq\; t,\; u\; \backslash neq\; n+1-t)$ 。

取 $i=u\mathrm{，}j=ti=u\; ，\; j=t$ ，得 $a_u=n+1-ta\_\{u\}=n+1-t$ 。

取 $i=n+1-t\mathrm{，}j=u\mathrm{，}{a}_n+1-t=n+1-ui=n+1-t\; ，\; j=u\; ，\; a\_\{n\}+1-t=n+1-u$ 。

取 $i=n+1-u,j=n+1-ti=n+1-u,\; j=n+1-t$, 得 $a_n+1-u=ta\_\{n\}+1-u=t$ 。

由于$u\mathrm{\ne }t,u\mathrm{\ne }n+1-tu\ne t,u\ne n+1-t$,观察上述等式发现等号右边的四个数两两不同。

进而将此$44$个数分成形如$(u,n+1-V)(u,n+\; 1\; -\; V\; )$的两组。可找到这样的四元数组其在排列的相同位置是相同的四个数，但顺序不同。

因此可以通过如下步骤得到全部排列：

1.取最小的整数$KK$，使得$a_{k}a\_k$待定，进而求出$a_u\mathrm{，}{a}_n+1-u\mathrm{，}{a}_n+1-ka\_u，a\_n\; +1-u，a\_n+1-\; k$。

2.重复上述过程。

显然答案$=2\times 6\times \mathrm{10...}\times (n-2)=2\; \backslash times\; 6\backslash times10...\; \backslash times(n-2)$。

所以答案等价于$\frac{\frac{n}{2}!}{\frac{n!}{4}!}\backslash frac\{\backslash frac\{n\}\{2\}\; !\}\{\backslash frac\{n\; !\}\{4\}\; !\}$

#include<bits/stdc++.h>
#define Mod 998244353
#define N 2000005
using namespace std;
int n,fac[N];
inline int ksm(int x,int y){
	int ans1=1;while (y){
		if (y&1) ans1=1ll*ans1*x%Mod;
		y>>=1;x=1ll*x*x%Mod;
	}return ans1;
}
int main(){
	scanf("%d",&n);fac[0]=1;
	if (n==1) return puts("1"),0;
	if (n&3) return puts("0"),0;
	for (int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%Mod;
	printf("%lld\n",1ll*fac[n/2]*ksm(fac[n/4],Mod-2)%Mod);
	return 0;
}