Fence Building2017亚洲乌鲁木齐

Fence Building

Time limit1000 msMemory limit262144K

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.

Input The first line contains an integer $1\le T\le 100000$, the number of test cases. For each test case, there is one line that contains an integer n. It is guaranteed that $1\le T\le 10^5$ and $1\le n\le 10^{18}$.

Output For each test case, you should output a line ”Case #i: ans” where i is the test case number, starting from 1 and ans is the remainder of the maximum number of cows farmer John can feed when divided by $10^9+7$.

Sample Input 3 1 3 5

Sample Output Case #1: 1 Case #2: 4 Case #3: 16

题意就是一个圆，给你 $n$ 个在圆周上的点，每个点两两连线，问这些线最多把圆分成几部分

圆周上每条边多分出一个区域，每两条边可以多产生一个交点，相当于又多了一个区域，再加上圆本身具有的区域 $1$ 因为给的是点的数量，两个点连城一条边所以总和是$C(n,2)+C(n,4)+1$ 对 $n<=4$ 的情况特判一下，这里用O1快速乘和求逆元写

#include <bits/stdc++.h> using namespace std; #define MOD 1000000007 #define ll long long inline ll mu(ll x,ll y)//O1快速乘 { return (x*y-(ll)((long double)x/MOD*y)*MOD+MOD)%MOD; } ll quick_pow(ll a,ll b,ll mod){ ll ans=1; while(b) { if(b&1) ans=(ans*a)%mod; a=(a*a)%mod; b>>=1; } return ans; } ll inv(ll x,ll mod){ return quick_pow(x,mod-2,mod); } int main() { ll n; int T; cin>>T; int t=1; while(T--){ scanf("%lld", &n); ll ans=0; if(n==1){ printf("Case #%d: 1\n", t++); continue; } if(n==2){ printf("Case #%d: 2\n", t++); continue; } if(n==3){ printf("Case #%d: 4\n", t++); continue; } if(n==4){ printf("Case #%d: 8\n", t++); continue; } ll a1=mu(mu(mu(n,n-1),n-2),n-3); ll a2=mu(n,n-1); ans=(mu(a1,inv(24,MOD))+mu(a2,inv(2,MOD))+1)%MOD; printf("Case #%d: %lld\n", t++, ans); } return 0; }