洛谷p1426，洛谷—— P1375 小貓

2023-11-19 阅读 14 评论 0

摘要：https://www.luogu.org/problemnew/show/1375 題目描述有2n只小貓站成一圈，主人小明想把它們兩兩之間用繩子綁住尾巴連在一起。同時小明是個完美主義者，不容許看到有兩根繩子交叉。請問小明有幾種連線方案，可以把讓所有小貓兩兩配對？方案數很大

https://www.luogu.org/problemnew/show/1375

題目描述

有2n只小貓站成一圈，主人小明想把它們兩兩之間用繩子綁住尾巴連在一起。同時小明是個完美主義者，不容許看到有兩根繩子交叉。請問小明有幾種連線方案，可以把讓所有小貓兩兩配對？

方案數很大，僅需輸出方案數模1000000007（一個質數）的值。

數據范圍:

60% N<=100

100% N<=100000

輸入輸出格式

洛谷p1426、輸入格式：

輸入一個整數n

輸出格式：

輸出方案數對1000000007取模的值

輸入輸出樣例

輸入樣例#1：?復制

輸出樣例#1：?復制

5


卡特蘭數組合公式C(2*n,n)-C(2*n,n-1)

 1 #include <cstdio>
 2 
 3 #define LL long long
 4 
 5 inline void read(int &x)
 6 {
 7     x=0; register char ch=getchar();
 8     for(; ch>'9'||ch<'0'; ) ch=getchar();
 9     for(; ch>='0'&&ch<='9'; ch=getchar()) x=x*10+ch-'0';
10 }
11 
12 const int P(1000000007);
13 
14 LL fac[500005];
15 
16 inline LL Pow(LL a,LL b)
17 {
18     LL ret=1;
19     for(; b; b>>=1,a*=a,a%=P)
20         if(b&1) ret*=a,ret%=P;
21     return (int)ret;
22 }
23 
24 LL C(LL n,LL m)
25 {
26     return fac[n]*Pow(fac[m],P-2)%P*Pow(fac[n-m],P-2)%P;
27 }
28 
29 int Presist()
30 {
31     int n; read(n); fac[0]=1;
32     for(int i=1; i<=n<<1; ++i) fac[i]=1ll*fac[i-1]*i%P;
33     printf("%lld\n",(C(n<<1,n)-C(n<<1,n-1)+P)%P);
34     return 0;
35 }
36 
37 int Aptal=Presist();
38 int main(int argc,char**argv){;}