題目描述
METO 喜歡吃披薩，同時(shí)他又是一個(gè)對(duì)幾何美學(xué)頗有研究的人鲜侥。
對(duì)于一個(gè)披薩嗅剖，METO 首先會(huì)在邊緣隨機(jī)取 n
n 個(gè)不重復(fù)的點(diǎn)抵乓，然后每?jī)牲c(diǎn)連一條線爷怀。
METO 想知道沿著這些線切披薩最多可以將其分為幾份缎除？
輸入格式
第一行為數(shù)據(jù)組數(shù) T,(1 \le T \le 100)
T(1≤T≤100)接下去 T
T 行脯宿，每行一個(gè)正整數(shù) n,(1 \le n \le 10^{9})
n(1≤n≤10?9??)
輸出格式
對(duì)每組數(shù)據(jù)輸出一行 ans
ans直晨，表示能分的份數(shù)亩进，答案對(duì) 10^9+7
10?9??+7 取模
樣例數(shù)據(jù)
輸入
512345
輸出
124816
題解:由歐拉定理得：V+F-E=2,V為頂點(diǎn)個(gè)數(shù)症虑，F(xiàn)為平面數(shù)目，E為邊的數(shù)目归薛。容易知道谍憔，在多邊形內(nèi)的交點(diǎn)的個(gè)數(shù)為C(n,4),因?yàn)槊克膫€(gè)點(diǎn)形成一個(gè)交點(diǎn)。所以V=n+C(n,4)主籍。因?yàn)橥耆珗D的邊數(shù)為C(n,2),還要加上圓邊上的n條邊习贫。又因?yàn)槎噙呅蝺?nèi)部的邊的交點(diǎn)會(huì)導(dǎo)致邊的數(shù)目的增加，而在遍歷多邊形內(nèi)部的邊時(shí)千元，因?yàn)榻稽c(diǎn)都是由兩條邊相交形成的苫昌，所以那些遍歷那些邊的時(shí)候，交點(diǎn)都會(huì)被訪問(wèn)兩次幸海，也就是新增的邊數(shù)為2C(n,4)祟身。所以邊數(shù)一共為n+C(n,2)+2C(n,4),推出F為C(n,2)+C(n,4)+2;而答案不包括圓外部的那個(gè)面，所以答案為C(n,2)+C(n,4)+1.
https://scut.online/problem.php?id=72
/*
根據(jù)費(fèi)馬小定理：
已知(a, p) = 1物独，則 a^（p-1） ≡ 1 (mod p), 所以 a*a^(p-2) ≡ 1 (mod p)袜硫。
也就是 (m!)的取模逆元為 (m!)^p-2 ；
*/
#include <cstdio>
#include<algorithm>
#include <stdlib.h>
#include<string.h>
#define maxn 1000010
using namespace std;
typedef long long LL;
const LL mod=1000000007;
LL quick(LL a,LL b)
{
LL res=1,base=a;
while(b)
{
if(b&1) res=(res*base)%mod;
b>>=1;
base=(base*base)%mod;
}
return res;
}
LL combine(LL n,LL m)
{
if(n<m) return 0;
LL ans=1,ca=1,cb=1;
for(LL i=0;i<m;i++)
{
ca=(ca*(n-i))%mod;
cb=(cb*(m-i))%mod;
}
ans=(ca*quick(cb,mod-2))%mod;
return ans;
}
LL Lucas(LL n,LL m)
{
if(m==0) return 1;
return combine(n%mod,m%mod)*Lucas(n/mod,m/mod);
}
int main()
{
int t;
scanf("%d",&t);
LL n,res;
while(t--)
{
scanf("%lld",&n);
res=(Lucas(n,2)+Lucas(n,4)+1)%mod;
printf("%lld\n",res);
}
}
