問題：おもしろい数列#
説明#
長さ 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 のおもしろい数列の異なる個数を求めてください。最終的な答えは P で割った余りを出力するだけです。
入力#
スペースで区切られた 2 つの整数 n と P。
出力#
1 つの整数のみを含む行で、長さ 2n のおもしろい数列の個数を 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 行に並べ、右側が左側よりも大きく、後ろが前よりも大きいようにする場合の数を求めます。
奇数を 1 行目とし、偶数を 2 行目として扱えば良いです。
次に、データが非常に大きいことに気づきます。再帰式には除算が含まれており、p も素数ではないため、逆元を使用することはできません（私も逆元を知りません、私はとても弱いです）。
したがって、この一般項を使用する必要があります。
少し変形します。
このように変形することで、特殊な方法で約分できます。
1 から 2n までのすべての素数を列挙し、それぞれの $n,(n+1),2n$ におけるその素数の出現回数(cnt1,cnt2,cnt3)を計算します。
そして、答えに $primes_i^{(cnt3-cnt2-cnt1)}$ を加算乗算します。
ここで加算ではなく乗算であることに注意してください。私は間違えました
コード#
//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;
}