[卡特兰数][大组合数取模] BZOJ 1485

https://cn.vjudge.net/contest/243050#problem/E

手推几项可以看出是卡特兰数，具体证明 https://blog.csdn.net/Bfk_zr/article/details/78313960

这个题最神奇的是学到了O(n)求对非任意数组合数取模的方法！（适用于n<1e7)

具体做法：筛出1-n中所有质数，筛出每个数最小的质因子p[i]。
开一个cnt[n]的数组。
for(i=n~1) 对于每个i（质数跳过），拆成两个数p[i]和i/p[i]，cnt[p[i]]和cnt[i/p[i]]都加上cnt[i]，cnt[i]赋为0。
这样之后cnt[p]存的就是质因子p的指数。
因为n以内的质数有 n/logn 个,for每个指数，快速幂是log的，因此最终求C(n,m)的复杂度是O(n)的。
这个东西的思想其实在书上看到过，但是那个是必须先求出来分子分母上数字的质因数，复杂度还是nsqrt(n)的，这个的话在筛的过程中只求出了每个数的最小质因数，然后利用类似于分治的每次都往下推，最后就得到了正确结果而不用把所有的都做了ooooorz

Talk is cheap

 

#include
#include
#include
#include
#define LL long long
using namespace std;
const int N=2000005;
const int M=1000000005; 
int n,mod,cnt[N],pri[N],ptot=0,p[N];
bool is[N];
void shai()
{
    is[1]=1; p[1]=1;
    for(int i=2;i<=2e6;i++)
    {
        if(!is[i]) {pri[++ptot]=i; p[i]=i;}
        for(int j=1;j<=ptot;j++)
        {
            int pp=pri[j];
            LL x=1LL*pp*i;
            if(x>2e6) break;
            is[x]=1; p[x]=pp;
            if(i%pp==0) break;
        }
    }   
}
void add(int x,int val)
{
    cnt[x]+=val;
    if(is[x]&&x!=1) {cnt[p[x]]+=cnt[x]; cnt[x/p[x]]+=cnt[x]; cnt[x]=0;}
}
int modpow(int A,int B)
{
    int ans=1; int base=A;
    for(;B;B>>=1)
    {
        if(B&1) ans=(1LL*ans*base)%mod;
        base=(1LL*base*base)%mod;
    }
    return ans;
}
int main()
{
    shai();
    scanf("%d%d",&n,&mod); //ans=C(2n,n)/(n+1)=(2n*(2n-1)*...*n)/n!
    for(int i=2*n;i>n+1;i--) add(i,1);//分子上
    for(int i=n;i>=1;i--) add(i,-1);//分母上
    for(int i=2*n;i>=1;i--) add(i,0);//再过滤一遍（似乎没有必要？
    int ans=1;
    for(int i=1;i<=ptot&&pri[i]<=2*n;i++)
    ans=(1LL*ans*modpow(pri[i],cnt[pri[i]]))%mod;
    printf("%d\n",ans);
    return 0;
}