概率公式华东理工月赛 - 站军姿 _题目

题目链接：点击查看
题目大意：在圆上随机生成n个点，求n个点在同一侧的概率
题目分析：做这个题的时候感觉是数论，从网上搜了一下题面，搜到了一个算法，没看懂证明，只是看懂了式子（式子谁看不懂。。），大佬博客：，公式：

文章插图
然后就尝试实现，因为涉及到了求逆元，恰好模又是一个素数，所以直接用费马小定理求一下逆元，实现一下就好了
就好了？
这个题的细节很多，下面一一列举：
初始时n可能比1e9+7要大，所以需要对n取模题目要求的是P/Q的最简情况，所以需要同除gcd化简当n对1e9+7取模后，设a=n9+7 ，对原公式求2的幂时还是需要求n-1次方，而不是,求a-1次方
上代码吧，这个破题因为一开始没对n取模， WA了六七发
【概率公式华东理工月赛 - 站军姿】

#include#include#include#include#include #include #include#includeusing 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;}

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

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