https://www.luogu.org/problem/show?pid=3200
首先，我們不能保證要求的數的逆元和模域互質；
所以我們要用分解質因數來抵消除法；
其實逆元的話即使可行也會超時；
那么我轉載了，實在沒什么可以說的；
另外卡特蘭數
http://baike.baidu.com/link?url=St3mmth0khr1jUoD9Vwdroupnfajo6hhTSgwvOkjAPrP0Htt12nZjsMue4T_5JhMopRqlhgAkCt2dDzd378Kg8xjsSYwGn3J_CMLgsvI4Psdhj3z0s4zTucxc1v6dRlP
話說這個方法好巧妙啊
http://blog.csdn.net/jiangshibiao/article/details/24009239
【轉化】就是求卡特蘭數。
【初始代碼】
#include<cstdio>
using namespace std;
typedef long long ll;
ll prime[200005],a[200005];
bool f[2000005];
ll temp,n,p,i,j,cnt,mod;
ll pow(ll a,ll b)
{ ll ans; for (ans=1;b;b>>=1,a=a*a%mod) if (b&1) ans=ans*a%mod; return ans;
}
int main()
{ scanf("%lld%lld",&n,&mod); for (i=2;i<=n*2;i++) { if (!f[i]) prime[++cnt]=i; for (j=1;j<=cnt&&prime[j]*i<=n*2;j++) f[prime[j]*i]=true; } for (i=n+2;i<=n*2;i++) for (j=1,p=i;j<=cnt&&p;j++) while (p%prime[j]==0) a[j]++,p/=prime[j]; for (i=2;i<=n;i++) for (j=1,p=i;j<=cnt&&p;j++) while (p%prime[j]==0) a[j]--,p/=prime[j]; temp=1; for (j=1;j<=cnt;j++) if (a[j]) temp=(temp*pow(prime[j],a[j]))%mod; printf("%lld",temp);for (;;); return 0;
} 用歐拉篩法，O（n）的效率求出每個質數。然后枚舉階乘，像質數表一樣把一個數給分解。但是效率很低。
【優化1】如果一個數是合數，我們可以把它的某個因子記下來。然后我們同樣從開始枚舉階乘，而且是倒著枚舉。對于每個數，如果它是合數，我就把它分解。比如，設f[n]為結果中含有n因子的個數。u是n的一個約數。那么我們可以f[u]+=f[n],f[n/u]+=f[n]。這樣就不用多次用快速冪了。直到n是質數為止。
【優化2】開始可以把1–n的f[i]設為-1，把n+2–2*n(注意，最后要除n+1,所以從n+2開始)的f[i]設為1.這樣只需1次循環。
【AC代碼】
#include<cstdio>
using namespace std;
typedef long long ll;
ll prime[200005],a[2000005],come[2000005];
ll temp,n,p,i,j,cnt,mod;
ll pow(ll a,ll b)
{ ll ans; for (ans=1;b;b=b/2,a=a*a%mod) if (b&1) ans=ans*a%mod; return ans;
}
int main()
{ scanf("%lld%lld",&n,&mod); for (i=2;i<=n*2;i++) { if (!come[i]) prime[++cnt]=i; for (j=1;j<=cnt&&prime[j]*i<=n*2;j++) come[prime[j]*i]=i; } temp=1; for (i=2;i<=n;i++) a[i]=-1; for (i=n+2;i<=2*n;i++) a[i]=1; for (i=n*2;i>1;i--) if (come[i]) { a[come[i]]+=a[i]; a[i/come[i]]+=a[i]; } else temp=temp*pow(i,a[i])%mod; printf("%lld",temp); return 0;
} 
