題目：有趣的數列#
描述#
我們稱一個長度為 2n 的數列是有趣的，當且僅當該數列滿足以下三個條件：
(1) 它是從 1 到 2n 共 2n 個整數的一個排列 {Ai}；
(2) 所有的奇數項滿足 A1<A3<…<A2n-1，所有的偶數項滿足 A2<A4<…<A2n；
(3) 任意相鄰的兩項 A2i-1 與 A2i (1≤i≤n) 滿足奇數項小於偶數項，即：A2i-1<A2i。
現在的任務是：對於給定的 n，請求出有多少個不同的長度為 2n 的有趣的數列。因為最後的答案可能很大，所以只要求輸出答案 mod P 的值。
輸入#
用空格隔開的兩個整數 n 和 P。
輸出#
僅含一個整數，表示不同的長度為 2n 的有趣的數列個數 mod P 的值
輸入範例 1#
3 10
輸出範例 1#
5
輸入範例 2#
10 1013
輸出範例 2#
588
輸入範例 3#
675546 14358205
輸出範例 3#
1511390
提示#
對於範例 1：對應的 5 個有趣的數列分別為
（1,2,3,4,5,6），（1,2,3,5,4,6），（1,3,2,4,5,6），（1,3,2,5,4,6），（1,4,2,5,3,6）。
50% 的數據滿足 n≤1000 ，100% 的數據滿足 n≤1000000 且 P≤1000000000。
思路#
首先發現它是個卡特蘭數
-
硬算前幾項的數字規律（我是這樣做的）
-
可以轉換為一個典型的卡特蘭數的例子：
n 個數排成兩行，使右邊都大於左邊，後邊都大於前邊，求排法數量
將奇數看成第一行，將偶數看成第二行即可。
然後發現數據很大，遞推式都有除法，p 也不是質數不能用逆元（雖然我也不回逆元我太弱了）
所以要用這個通項式
化一下
這樣化的作用是可以用特殊的方法約分
枚舉 1~2n 的所有質數
然後分別計算 $n,(n+1),2n$ 中那個質數的次數(cnt1,cnt2,cnt3)
再往答案中加乘上 $primes_i^{(cnt3-cnt2-cnt1)}$ 就好了
注意這裡是乘不是加我就是這樣錯的
Code#
//I closed myself.What a happy zero-boomed contest!!!
//上一行是考試自閉的時候寫的不要管
//(2n)!/(n!*n!*(n+1))
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL MAXN=1000000+5;
LL n,p,cnt;
bool v[MAXN];
LL primes[2*MAXN];
bool isHeshu[2*MAXN];
LL oula(LL x);//質數篩
LL qkpow(LL x,LL y);//快速冪
int main(){
// freopen("LLeresting.in","r",stdin);
// freopen("LLeresting.out","w",stdout);
scanf("%d%d",&n,&p);
oula(2*n);
LL ans=1;
for(LL i=1;i<=cnt;++i){
LL cnt1=0,cnt2=0,cnt3=0;
LL pm=primes[i];
while(pm<=2*n){
cnt1+=n/pm;
cnt2+=(n+1)/pm;
cnt3+=2*n/pm;
pm*=primes[i];//當前質因子次數+1
}
LL sl=cnt3-cnt1-cnt2;
ans*=qkpow(primes[i],sl);
ans%=p;
}
printf("%lld\n",ans);
// fclose(stdin);
// fclose(stdout);
return 0;
}
LL oula(LL x){
for(LL i=2;i<=x;++i){
if(!isHeshu[i]){
primes[++cnt]=i;
}
for(LL j=1;primes[j]*i<=x;++j){
isHeshu[primes[j]*i]=1;
if(i%primes[j]==0)break;
}
}
}
LL qkpow(LL x,LL y){
LL sum=x;
LL ret=1;
while(y){
if(y&1){
ret=ret*sum%p;
}
sum=sum*sum%p;
y>>=1;
}
return ret;
}