2017乌鲁木齐区域赛D题Fence Building-平面图的欧拉公式
这个题B站上面有这题很完整的分析和证明，你实在不懂，可以看看这个视频
https://www.bilibili.com/video/av19849697?share_medium=android&share_source=qq&bbid=00561DA9-126A-4190-88A8-2B9DD5DAFEB512211infoc&ts=1533979978895
视频里面讲的很清楚，我再重复一下把，就是说，给N个圆上的点，在这个圆内部会产生多少个点呢？，很简单C(N,4);为什么？？？因为园内任意四个点，可以连线组成一个内部点，再加上N个外围点，总共有N+C(n,4）个点，我们再来算有多少边，首先我们可以想，这些内部点一定不是端点，我可以考虑一下，一个不是端点的点，可以把线段分成多少部分呢？？？答案是2*C(N,4),然后我们把圆的外围弧，也变成线，那么就完美的用平面图的欧拉公式解决：
设G为任意的连通的平面图，则v-e+f=2，v是G的顶点数，e是G的边数，f是G的面数。
再把最外面的区域减去就行。
这里一定要注意取模的问题，由于N变态到离谱，我们不能对N有任何的操作，首先出来就必须把N%MOD，否则就会炸范围
这里你仔细一看，就发现，公式化简成为ans=C(n,2)+C(n,4)+1;处理一下逆元就好了
#include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> #define ll long long using namespace std; const ll mod = 1e9+7; ll qpow(ll a,ll b) { ll ans=1; while(b) { if (b&1)ans=(ans*a)%mod; a=(a*a)%mod; b>>=1; } return ans; } int main() { int t; ll n; int cas=0; scanf("%d",&t); while(t--){ scanf("%lld",&n); ll ans=(1+(((n%mod)*((n-1)%mod)%mod*qpow(2,mod-2))%mod)%mod+(((((n%mod)*((n-1)%mod))%mod*((n-2)%mod))%mod*((n-3)%mod))%mod*qpow(24,mod-2)%mod)%mod)%mod; printf("Case #%d: %lld\n",++cas,ans); } return 0; }
投递国家电网等公司10个岗位 >
查看18道真题和解析