题解 | 小红的好排列

#include<bits/stdc++.h>
#define int long long
using namespace std;
int const N = 1e6+9;
int const mod = 1e9+7;
int n;
int f[N],nf[N];

int ksm(int a,int b)
{
	if(!b) return 1;
	if(b == 1) return a % mod;
	int t = ksm(a,b/2);
	if(b & 1) return t * t % mod * a % mod;
	else return t * t % mod;
}

void pre()
{
	f[0] = 1;
	for(int i=1;i<=n;i++) f[i] = f[i-1] * i % mod;
	nf[n] = ksm(f[n],mod-2);
	for(int i=n-1;i>=0;i--) nf[i] = nf[i + 1] * (i + 1) % mod;
}
int C(int n,int m)
{
	if(m > n) return 0;
	return f[n] * nf[n-m] % mod * nf[m] % mod;
}

int A(int n,int m)
{
	if(m > n) return 0;
	return f[n] * nf[n-m] % mod;
}
//nfi * fi = 1
//nfi * fi-1 * i = 1
//nfi-1 = nfi * i 
signed main()
{
	cin>>n;
	pre();
	int a = n / 3;
	int b = n / 2;
	int c = 2 * a - b; 
	
	if(n > 3 && n % 2 == 0)	cout<<C(a,c) * C(a,c) % mod * A(c,c) % mod * A(n-a,a-c) % mod * A(n-a,n-a) % mod; 
	else cout<<0;
	return 0;
} 
/*
1 2 3 4
a = 1
b = 2
c = 0
*/ 

一道排列组合题目，也是准备华为机考的第一道题。

手玩一下4,6,8

定义三个变量

a：3的倍数的下标数量

b：目标位置数量

c：需要i与a[i]同时为3的倍数的位置数量 c = 2 * a - b

先安排c，C(a,c) * C(a,c) * A(c,c)

再安排剩下的3的倍数 A(n-a,a-c)

余下的数全排列 A(n-a,n-a)