HPU-1029-QAQ的填充方案【組合數】【卡特蘭數】

題目連結：​​點選打開連結​​

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;
}