华东理工月赛 - 站军姿(概率公式)

题目链接：点击查看

题目大意：在圆上随机生成n个点，求n个点在同一侧的概率

题目分析：做这个题的时候感觉是数论，从网上搜了一下题面，搜到了一个算法，没看懂证明，只是看懂了式子（式子谁看不懂。。），大佬博客：https://blog.csdn.net/zmazon/article/details/8547278，公式：

然后就尝试实现，因为涉及到了求逆元，恰好模又是一个素数，所以直接用费马小定理求一下逆元，实现一下就好了

就好了？

这个题的细节很多，下面一一列举：

1. 初始时n可能比1e9+7要大，所以需要对n取模
2. 题目要求的是P/Q的最简情况，所以需要同除gcd化简
3. 当n对1e9+7取模后，设a=n%1e9+7，对原公式求2的幂时还是需要求n-1次方，而不是,求a-1次方

上代码吧，这个破题因为一开始没对n取模，WA了六七发

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm> 
#include<queue> 
#include<set>
#include<string>
using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;const int mod=1e9+7;LL qpow(LL a,LL b)
{LL ans=1;while(b){if(b&1){ans=ans*a%mod;}b>>=1;a=a*a%mod;}return ans;
}LL gcd(LL a,LL b)
{return b==0?a:gcd(b,a%b);
}int main()
{int w;cin>>w;while(w--){LL n;scanf("%lld",&n);LL a=n%mod;//这里记得取模LL temp=qpow(2,n-1);LL d=gcd(a,temp);a/=d;temp/=d;temp=qpow(temp,mod-2);//费马小定理求逆元	printf("%lld\n",a*temp%mod);}return 0;
}