題目連結:點選打開連結
1029: QAQ的填充方案
時間限制: 1 Sec
記憶體限制: 128 MB
送出: 17
解決: 4
[
送出][
狀态][
讨論版]
題目描述
給定1−2∗N
1−2∗N共2∗N
2∗N個元素,現在有x[1−N],y[1−N]
x[1−N],y[1−N]兩個數組,你需要把這2∗N
2∗N個數(每個數必須用一次且僅用一次)填入這兩個數組裡面。
定義一個填充方案是合法的即:
x[i]<x[i+1]<x[i+2]<...<x[N]
x[i]<x[i+1]<x[i+2]<...<x[N]
y[i]<y[i+1]<y[i+2]<...<y[N]
y[i]<y[i+1]<y[i+2]<...<y[N]
x[i]<y[i],x[i+1]<y[i+1],...,x[N]<y[N]
x[i]<y[i],x[i+1]<y[i+1],...,x[N]<y[N]。
輸入
第一行輸入一個整數T
T,代表有T
T組測試資料。
每組資料輸入一個整數N
N,代表有N
N個位置。
注:1<=T<=30,1<=N<=1000000
1<=T<=30,1<=N<=1000000。
輸出
對每組測試資料,輸出一個整數代表合法的填充方案數。
由于結果很大,請對(109+7)
(109+7)取餘。
樣例輸入
2
1
2
樣例輸出
1
2
提示
對于第二組測試資料,有1,2,3,4
1,2,3,4共4
4個數。填數方案有:
(1)x[1]=1,x[2]=2
x[1]=1,x[2]=2
y[1]=3,y[2]=4
y[1]=3,y[2]=4
滿足1<2,3<4,1<3,2<4
1<2,3<4,1<3,2<4。
(2)1,3
1,3
2,4
2,4
同上。
來源
#include<cstdio>
#include<algorithm>
#include<cstring>
#define LL long long
using namespace std;
const LL MOD=1e9+7;
LL n;
LL fac[2000010];
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;
}
LL C(LL a,LL b)
{
return fac[a]*qpow(fac[b],MOD-2)%MOD*qpow(fac[a-b],MOD-2)%MOD;
}
int main()
{
fac[0]=1;
for(int i=1;i<=2000000;i++)
fac[i]=fac[i-1]*i%MOD;
int t;
scanf("%d",&t);
while(t--)
{
scanf("%lld",&n);
printf("%lld\n",C(2*n,n)*qpow((n+1),MOD-2)%MOD); // 最後也要逆元一下啊
}
return 0;
}