礼物

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 3248 字
n件礼物分给m个人，第i个人要w_i件，求分
一本通
练习
正文

/*
原题：T1659「一本通 6.6 练习 8」礼物
题意：n 件礼物分给 m 个人，第 i 个人要 w_i 件，求分配方案数模 P；无解输出 Impossible。
思路：答案是 Π_i C(n-Σ_{j<i}w_j, w_i)。P 不一定是素数，故用扩展 Lucas：
把 P 分解成素数的幂 Π p^e，对每个 p^e 用"去掉所有 p 因子后的阶乘"算出
C(N,M) mod p^e，其中 p 的指数单独用 Legendre 公式统计；最后用 CRT 合并回模 P。
复杂度：时间 O(m·P·log n)，空间 O(P)
易错点：1) 模数合数时不能直接用费马小定理求逆，要用扩展欧几里得，
且只对被除数中"去掉 p 因子后"的部分求逆（那部分与 p 互素）；
2) 组合数中 p 的指数要用 cnt(n)-cnt(m)-cnt(n-m) 单独算出来再乘回去；
3) 若 Σw_i>n 则无解，先判断再计算。
*/
#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;
}
// n! 中去掉全部 p 因子后对 pe 取模
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 exLucasC(long long n,long long m,long long p,long long pe){
    if(m<0 || m>n){
        return 0;
    }
    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(n,p,pe,f);
    long long b=facNoP(m,p,pe,f);
    long long c=facNoP(n-m,p,pe,f);
    long long cnt=cntP(n,p)-cntP(m,p)-cntP(n-m,p);
    long long res=a*invMod(b,pe)%pe*invMod(c,pe)%pe;
    res=res*modPow(p,cnt,pe)%pe;
    return res;
}
long long Cmod(long long n,long long m,long long mod){
    if(m<0 || m>n){
        return 0;
    }
    long long tmp=mod;
    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=exLucasC(n,m,p,pe);
        long long mi=mod/pe;
        ans=(ans+ai*mi%mod*invMod(mi%pe,pe)%mod)%mod;
    }
    return ans;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    long long P,n;
    cin>>P>>n;
    int m;
    cin>>m;
    vector<long long> w(m);
    long long sum=0;
    for(int i=0;i<m;i++){
        cin>>w[i];
        sum+=w[i];
    }
    if(sum>n){
        cout<<"Impossible\n";
        return 0;
    }
    long long ans=1;
    long long rest=n;
    for(int i=0;i<m;i++){
        ans=ans*Cmod(rest,w[i],P)%P;
        rest-=w[i];
    }
    cout<<ans<<"\n";
    return 0;
}
礼物

正文

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