問題：興味深い数列#
説明#
私たちは、長さが 2n の数列を興味深いと呼びます。これは、次の 3 つの条件を満たす場合に限ります：
(1) それは 1 から 2n までの 2n 個の整数の並び {Ai} です；
(2) すべての奇数項は A1<A3<…<A2n-1 を満たし、すべての偶数項は A2<A4<…<A2n を満たします；
(3) 任意の隣接する 2 項 A2i-1 と A2i (1≤i≤n) は、奇数項が偶数項より小さいことを満たします。すなわち：A2i-1<A2i。
現在のタスクは：与えられた n に対して、長さが 2n の異なる興味深い数列がいくつあるかを求めることです。最終的な答えは非常に大きくなる可能性があるため、答えを mod P の値として出力する必要があります。
入力#
空白で区切られた 2 つの整数 n と P。
出力#
1 つの整数のみを含み、異なる長さが 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 個の数を 2 行に並べ、右側がすべて左側より大きく、後ろ側がすべて前側より大きくなるように、並べ方の数を求めます。
奇数を第一行、偶数を第二行と見なせばよいです。
その後、データが非常に大きく、再帰式に除算が含まれていることに気づきます。p も素数ではないため逆元を使用できません（逆元は私もできないので、私は弱すぎます）
したがって、この一般項を使用する必要があります。
これを変形します。
この変形の目的は、特別な方法で約分できることです。
1~2n のすべての素数を列挙します。
次に、それぞれの $n,(n+1),2n$ の中でその素数の出現回数(cnt1,cnt2,cnt3)を計算します。
そして、答えに加乗算して $primes_i^{(cnt3-cnt2-cnt1)}$ を掛ければよいです。
ここでは加算ではなく乗算であることに注意してください。私はこれを間違えました。
コード#
//自分を閉じ込めました。なんて幸せなゼロ爆発コンテストでしょう!!!
//上の行は試験自閉のときに書いたもので、気にしないでください
//(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;
}