http://www.lydsy.com/JudgeOnline/problem.php?id=1485 这题我们可以先试试暴力求几个数的答案，或者也可以写一个递推O（n^2）（这样可以拿50分，虽然我没去写） 问同学说这就是一个裸的Catalan数！！！ 我表示我数学太弱了。。。。。。。。 Catalan数有好几个公式。。。 这题我们用其中的一个公式： 这里存在的问题是：
暴力枚举时间O（n^2）完美TLE题目所给模数p不一定与n互质，不能用逆元做所以这里C这个东西不能杨辉三角递推，但直接套公式又有除法又取模 这下怎么办。。。。。。。。。。。。。。。这题不能做了吗？！ 查了下网上的各大题解发现只要用分解质因数就能完美解决
what？质因数？！ 听起来好暴力啊啊啊啊啊 其实就是这么暴力QAQ 首先上组合数公式： 考虑到这里的m就是2n，所以Catalan公式就可以化简成： （这里的π就是连乘的意思） 好了这样我们就可以做了:) 于是乎我们可以线性筛出1~2n之间的质数，然后把n+1~2n分解质因数一一放到桶里（各质数个数+1），把1~n分解质因数后把桶里的原来的质数减掉（各质数个数-1），最后把剩余所有质数乘起来取模就好了
先不急着晒代码，我们来谈谈怎么分解质因数 我是在线性筛质数时顺便记录每个数的最小的质因数，然后分解的时候我们可以直接把要处理的数除以它的最小质因数，然后丢到桶里，直到这个数变成1（滑稽） 。。。不懂的话（这个小学生都应该懂吧）我举个简单样例：18，设个桶数组t
18的最小质因数是2,t[2]+1,18/2=99的最小质因数是3，t[3]+1,9/3=33是质数（即它的最小质因数是3），t[3]+1，3/3=1数值=1，完成分解那么问题来了，怎么记录某数的最小质因数呢？？？ 使用线性筛方法（即欧拉筛）的同时，因为每个数只会被访问到一次，能访问到这个数的一定是它的最小质因数（这样保证时间O（n））
inline void get(){ for(int i=2;i<=2*n;i++){ if(!b[i])pri[++sum]=i,wei[i]=sum;//如果自己是质数最小质因数就是自己吧 for(int j=1;j<=sum;j++){ if(i*pri[j]>2*n)break; b[i*pri[j]]=1; wei[i*pri[j]]=j;//因为每个数只被访问一次，目前乘上的质数就是乘后数的最小质因数 if(i%pri[j]==0)break;//这个至关重要，这句话保证每个数只被访问一次而且是它的最小质因数，否则会被多次访问 } } }这里一段证明
i. 任何一个合数都可以表示成一个质数和一个数的乘积 ii. 假设A是一个合数，且A = x * y，这里x也是一个合数，那么有: A = x * y; (假设y质数，x合数) x = a * b; (假设a是质数，且a < x) =》 A = a * b * y = a * Z (Z = b * y) 即一个合数(x)与一个质数(y)的乘积可以表示成一个更大的合数(Z)与一个更小的质数(a)的乘积嗯好了这样就万事俱备啦 听说机房某位神犇用pow完美解决质因数，在这里%%%一下（反正这种做法我不会）
#include<bits/stdc++.h> using namespace std; int n,sum=0,MOD; long long ans=1; bool b[2000010]={0}; int pri[2000010]={0},wei[2000010]={0},c[2000010]={0}; inline void get(){ for(int i=2;i<=2*n;i++){ if(!b[i])pri[++sum]=i,wei[i]=sum; for(int j=1;j<=sum;j++){ if(i*pri[j]>2*n)break; b[i*pri[j]]=1; wei[i*pri[j]]=j; if(i%pri[j]==0)break; } } } inline void add(int x,int y){while(x!=1){c[wei[x]]+=y;x/=pri[wei[x]];}} inline void gans(int x){while(c[x]--)ans=(ans*pri[x])%MOD;} int main() { scanf("%d%d",&n,&MOD); get(); for(int i=n+1;i<=2*n;i++)add(i,1); for(int i=1;i<=n+1;i++)add(i,-1); for(int i=1;i<=sum;i++)gans(i); printf("%lld",ans); return 0; }