一眼卡特兰数...写完才发现不对劲，样例怎么输出$0$...原来模数不一定是质数= =...
第一次见到模数不是质数的求组合数方法$(n,mleq 10^7)$，记录一下...
先对于$1$~$n$的每个数筛出最小的质因子（我肯定是写埃式筛啦），那么乘上一个数$x$相当于乘上$x$的所有质因子，所以从大到小扫一遍每一个数，若$x$被乘了$1$次且$x$不是质数，那么就给$x$的最小质因子$mn_x$和$frac{x}{mn_x}$的次数+$1$，显然这样最后只会剩下质因子有记录次数，那么这个次数就是质因子的指数了。
如果求$C(n,m)$，不妨设$n-mleq m$，那么$m+1$~$n$被乘了$1$次，$1$~$n-m$被除了$1$次，也就是被乘了$-1$次，那么这些数的质因子都应该被减去相应次数。会不会有质因子被减到负数了？我们知道组合数一定是正整数，所以肯定不会出负数啦~
最后扫一遍所有质数，快速幂一下就可以求得组合数了，$n$以内的质数个数是$O(frac{n}{logn})$级别的，快速幂是$O(logn)$的，所以复杂度是$O(n)$的。
对于这题使用卡特兰数的$C(2n,n)/(n+1)$的公式会比较好一些，不算$n+1$的贡献就好了
#include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<algorithm> #define ll long long using namespace std; const int maxn=2000010, inf=1e9; int n, mod, ans; int p[maxn], mn[maxn], cnt[maxn]; bool v[maxn]; inline void read(int &k) { int f=1; k=0; char c=getchar(); while(c<'0' || c>'9') c=='-'&&(f=-1), c=getchar(); while(c<='9' && c>='0') k=k*10+c-'0', c=getchar(); k*=f; } inline void getp() { for(int i=2;i<=n<<1;i++) if(!v[i]) { p[++p[0]]=i; for(int j=i<<1;j<=n<<1;j+=i) v[j]=1, !mn[j] && (mn[j]=i); } } inline int power(int a, int b) { int ans=1; for(;b;b>>=1, a=1ll*a*a%mod) if(b&1) ans=1ll*ans*a%mod; return ans; } inline void add(int x, int delta) { cnt[x]+=delta; if(v[x]) { cnt[mn[x]]+=cnt[x]; cnt[x/mn[x]]+=cnt[x]; cnt[x]=0; } } int main() { read(n); read(mod); getp(); ans=1; for(int i=n<<1;i>n+1;i--) add(i, 1); for(int i=n;i>1;i--) add(i, -1); for(int i=1;i<=p[0];i++) ans=1ll*ans*power(p[i], cnt[p[i]])%mod; printf("%d ", ans); }