有趣的数列

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 2717 字
求长度为2n的"有趣的数列"个数对P取模
一本通
练习
正文

/*
原题：T1661「一本通 6.6 练习 10」有趣的数列
题意：求长度为 2n 的"有趣的数列"个数对 P 取模（即第 n 个 Catalan 数模 P）。
思路：Catalan(n)=C(2n,n)/(n+1)=(2n)!/(n!·(n+1)!)。P 不一定是素数，
故仍用扩展 Lucas：分解 P=Π p^e，对每个 p^e 用"去掉 p 因子的阶乘"分别算出
(2n)!、n!、(n+1)! 的互素部分，p 的指数单独用 Legendre 公式统计后乘回，
再对互素部分求逆（扩展欧几里得），最后 CRT 合并。
复杂度：时间 O(P·log n)，空间 O(P)
易错点：1) 分母是 n!·(n+1)!，别写成 (n+1)·n!·n!；
2) p 的指数要按 cnt(2n)-cnt(n)-cnt(n+1) 计算，Catalan 是整数故该值非负；
3) 对 p^e 求逆只适用于与 p 互素的部分，含 p 的部分不能求逆。
*/
#include <bits/stdc++.h>
using namespace std;
long long exgcd(long long a,long long b,long long& x,long long& y){
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    long long x1,y1;
    long long g=exgcd(b,a%b,x1,y1);
    x=y1;
    y=x1-(a/b)*y1;
    return g;
}
long long invMod(long long a,long long mod){
    long long x,y;
    exgcd(a,mod,x,y);
    x%=mod;
    if(x<0){
        x+=mod;
    }
    return x;
}
long long modPow(long long a,long long n,long long mod){
    long long r=1%mod;
    a%=mod;
    while(n>0){
        if(n&1){
            r=r*a%mod;
        }
        a=a*a%mod;
        n>>=1;
    }
    return r;
}
long long facNoP(long long n,long long p,long long pe,const vector<long long>& f){
    if(n==0){
        return 1;
    }
    return modPow(f[pe-1],n/pe,pe)*f[n%pe]%pe*facNoP(n/p,p,pe,f)%pe;
}
long long cntP(long long n,long long p){
    long long c=0;
    while(n>0){
        n/=p;
        c+=n;
    }
    return c;
}
long long catalanModPe(long long n,long long p,long long pe){
    vector<long long> f(pe);
    f[0]=1;
    for(long long i=1;i<pe;i++){
        if(i%p==0){
            f[i]=f[i-1];
        }else{
            f[i]=f[i-1]*i%pe;
        }
    }
    long long a=facNoP(2*n,p,pe,f);
    long long b=facNoP(n,p,pe,f);
    long long c=facNoP(n+1,p,pe,f);
    long long cnt=cntP(2*n,p)-cntP(n,p)-cntP(n+1,p);
    long long res=a*invMod(b,pe)%pe*invMod(c,pe)%pe;
    res=res*modPow(p,cnt,pe)%pe;
    return res;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    long long n,P;
    cin>>n>>P;
    long long tmp=P;
    vector<pair<long long,long long>> pf;
    for(long long d=2;d*d<=tmp;d++){
        if(tmp%d==0){
            long long e=0;
            while(tmp%d==0){
                tmp/=d;
                e++;
            }
            pf.push_back(make_pair(d,e));
        }
    }
    if(tmp>1){
        pf.push_back(make_pair(tmp,1));
    }
    long long ans=0;
    for(size_t i=0;i<pf.size();i++){
        long long p=pf[i].first;
        long long e=pf[i].second;
        long long pe=1;
        for(long long t=0;t<e;t++){
            pe*=p;
        }
        long long ai=catalanModPe(n,p,pe);
        long long mi=P/pe;
        ans=(ans+ai*mi%P*invMod(mi%pe,pe)%P)%P;
    }
    cout<<ans<<"\n";
    return 0;
}
有趣的数列

正文

一本通·提高篇的其它内容
