题解 | 小欧的排列计算

1.数论知识：两数相乘，只要其中一者为偶数，那么结果一定为偶数。扩展到该题，就是不能让两个奇数相邻，不难想到用隔板法来解决

2.假设有even个偶数，odd个奇数。先排偶数，因为数组是1~n，所以必须得要是放一隔一，第一个数可以是even个当中挑一个，第二个数可以是（even-1）个当中挑一个，得到 even!

3.现在天然形成了even+1个空，那么在even+1个空当中去填odd个数，则结果为 A(even+1,odd)，由于有顺序所以是排列不是组合

4.那么最后的结果为 even! * A(even+1,odd)

5.注意点：逆元（用费马小定理来求）+ even为 n/2 ＆ odd为 (n+1)/2 + 加法乘法一边取模一边算不影响最后结果

ac代码：

#include<iostream>
#define int long long
using namespace std;

int n;
const int MOD = 1e9 + 7,N = 1e5 + 10;
int g[N],f[N];//逆元数组+阶乘数组 

int qpow(int x,int y,int p)
{
	int ret = 1;
	x %= p;
	while(y)
	{
		if(y&1) ret = ret*x%MOD;
		x = x*x%MOD;
		y>>=1;
	}
	return ret;
}

void init()
{
	//初始化求逆元和阶乘
	f[0] = 1;
	for(int i=1;i<=n+1;i++) f[i] = f[i-1] * i % MOD;
	g[n+1] = qpow(f[n+1],MOD-2,MOD);
	for(int i=n+1;i>=1;i--)
		g[i-1] = g[i] * i % MOD;	
} 

int A(int a,int b)
{
	//排列公式 a!/(a-b)!
	return f[a] % MOD * g[a-b] % MOD;
}

signed main()
{
	cin>>n;
	init();
	//分别要求 even! 和 A(even+1,odd)
	int even = n/2;
	int odd = (n+1)/2;
	cout<<(f[even]*A(even+1,odd))%MOD;
	return 0;
}