题目链接:CF-1143E 简单的组合数学 对于给定的n个人，我们按照题意把他随机分为2组，得到分组系数 C n n / 2 {C_n^{n/2}} Cnn/2 考虑到这样均分为两组会出现均分出的两个集合A、B出现前后重复的情况， （A，B），（B，A） 在该系数上还需要除2，得到 C n n / 2 2 \frac{C_n^{n/2}}{2} 2Cnn/2 然后在完成分组后我们对每组的（n/2）人进行全排列，得到分组系数 n 2 ! \frac{n}{2}! 2n!，由于进行了全排列，而实际跳舞的人是围成了 一个圈，故实际有效的排列系数为 n 2 ! ÷ n 2 = ( n 2 − 1 ) ! \frac{n}{2}!÷\frac{n}{2}=(\frac{n}{2}-1)! 2n!÷2n=(2n−1)! 又因为有两个组别，每组的系数都是 ( n 2 − 1 ) ! (\frac{n}{2}-1)! (2n−1)! 最终的排列系数为 ( ( n 2 − 1 ) ! ) 2 ((\frac{n}{2}-1)!)^2 ((2n−1)!)2 所以我们的最终答案就是 C n n / 2 2 ∗ ( ( n 2 − 1 ) ! ) 2 \frac{C_n^{n/2}}{2}*((\frac{n}{2}-1)!)^2 2Cnn/2∗((2n−1)!)2
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <map> #include <queue> #include <functional> #include <vector> #include <stack> #include <set> #include <bitset> using namespace std; typedef long long ll; const int maxn=3e5+50; const int inf=0x7fffffff; const int mod=1e9+7; const int HASH=131; ll jiechen(ll n) { ll ans=1; for(int i=1;i<=n;i++) ans*=i; return ans; } int main() { int n; cin>>n; ll ans=jiechen(n)/(jiechen(n/2)*jiechen(n/2))*(jiechen(n/2-1)*jiechen((n/2-1)))/2; cout<<ans<<endl; return 0; }