2017乌鲁木齐区域赛D题Fence Building——欧拉定理

2017乌鲁木齐区域赛D题Fence Building——欧拉定理

题意：Farmer John owns a farm. He first builds a circle fence. Then, he will choose n points and build some straight fences connecting them. Next, he will feed a cow in each region so that cows cannot play with each other without breaking the fences. In order to feed more cows, he also wants to have as many regions as possible. However, he is busy building fences now, so he needs your help to determine what is the maximum number of cows he can feed if he chooses these n points properly.

思路：

欧拉定理：f = e - v + 2

v = n + C（n，4）（每4个点的连线必有一个交点）

e = n（圆弧） + C（n，2）+ 2*C（n，4）（一个交点是两条边形成的，这个交点将这两条边划分成4条边，数量上+2，因此有多少交点就增加交点数*2条边）

ans = f - 1,圆外的不算

#include #include #include #include using namespace std;typedef long long LL;const int mod = 1e9 + 7;LL power_mod(LL a,LL b){ LL base=a%mod; a=a%mod; LL res=1LL; while(b) { if(b&1) res=base*res%mod; base=base*base%mod; b=b>>1; } return res%mod;}LL C(LL n, LL m){ if(m > n) return 0; LL ans = 1; for(int i=1; i<=m; i++) { LL a = (n + i - m) % mod; LL b = i % mod; ans = ans * (a * power_mod(b, mod-2) % mod) % mod; } return ans;}LL Lucas(LL n, LL m){ if(m == 0) return 1; return C(n % mod, m % mod) * Lucas(n / mod, m / mod) % mod;}int main() { int T; scanf("%d", &T); for (int kase = 1; kase <= T; kase++) { LL n; scanf("%lld", &n); printf("Case #%d: %lld\n", kase, (Lucas(n, 2) + Lucas(n, 4) + 1) % mod); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。