欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

E. Two Round Dances(圆排列)Codeforces Round #677 (Div. 3)

程序员文章站 2022-06-04 18:51:19
...

原题链接: https://codeforces.com/contest/1433/problem/E

E. Two Round Dances(圆排列)Codeforces Round #677 (Div. 3)
测试样例

input
2
output
1
input
4
output
3
input
8
output
1260
input
20
output
12164510040883200

题意: n n n个人,平均分成两组,每组围成一个圆环跳舞,问有多少种组法。

解题思路: 组合数学问题中的圆排列。晚点补证明,有兴趣的可以百度看一下证明过程。

AC代码

/*
*邮箱:aaa@qq.com
*blog:https://me.csdn.net/hzf0701
*注:文章若有任何问题请私信我或评论区留言,谢谢支持。
*
*/
#include<bits/stdc++.h>	//POJ不支持

#define rep(i,a,n) for (int i=a;i<=n;i++)//i为循环变量,a为初始值,n为界限值,递增
#define per(i,a,n) for (int i=a;i>=n;i--)//i为循环变量, a为初始值,n为界限值,递减。
#define pb push_back
#define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define fi first
#define se second
#define mp make_pair

using namespace std;

const int inf = 0x3f3f3f3f;//无穷大
const int maxn = 1e5;//最大值。
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll>  pll;
typedef pair<int, int> pii;
//*******************************分割线,以上为自定义代码模板***************************************//

ll n;
ll f[25];
//c(n,m)
ll c(ll n,ll m){
	return f[n]/(f[n-m]*f[m]);
}
int main(){
	//freopen("in.txt", "r", stdin);//提交的时候要注释掉
	IOS;
	f[0]=f[1]=1;
	rep(i,2,20){
		f[i]=f[i-1]*i;
	}
	while(cin>>n){
		cout<<c(n,n/2)*f[n/2-1]*f[n/2-1]/2<<endl;
	}
	return 0;
}

相关标签: # CF 数论