NC206020. 弦
描述
给定一个圆，圆上有2N个互不重叠的点。每次操作随机选择两个先前未选择过的点连一条弦，共连成N条弦，求所有弦不交的概率。
输入描述
一行，只有一个整数N（1≤N≤107）。
输出描述
一行，即答案。答案应以模109+7的形式输出。正式的说，令M=109+7，答案可以表示为最简分数p/q的形式，其中p和q为整数且q与M互质。输出整数x满足 0≤x<M且 x⋅q ≡ p（mod M）。
示例1
输入:
2
输出:
666666672
C++14(g++5.4) 解法, 执行用时: 56ms, 内存消耗: 508K, 提交时间: 2020-08-13 22:56:00
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
long long fastpow(long long a,int b)
{
long long s=1;
for(;b;b>>=1,a=a*a%mod)if(b&1)s=s*a%mod;
return s;
}
int main()
{
int i,s=1,n;
scanf("%d",&n);
for(i=1;i<=n;i++)s=(long long)s*(i+1)%mod;
printf("%d\n",fastpow(2,n)*fastpow(s,mod-2)%mod);
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 54ms, 内存消耗: 384K, 提交时间: 2020-07-02 12:19:58
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
long long fastpow(long long a,int b)
{
long long s=1;
for(;b;b>>=1,a=a*a%mod)if(b&1)s=s*a%mod;
return s;
}
int main()
{
int i,s=1,n;
scanf("%d",&n);
for(i=1;i<=n;i++)s=(long long)s*(i+1)%mod;
printf("%d\n",fastpow(2,n)*fastpow(s,mod-2)%mod);
return 0;
}