洛谷2183 [国家集训队]礼物

题意

把 $n$ 个不同的礼物分给 $m$ 个人，每个人 $w_i$ 个，求方案数 $\mod p$ 的值。

其中 $n,p\le 10^{9}$ ，$m\le 5$ 。

题解

答案显然为：

$$\prod _{i=1}^m C(n-\sum_{i=1}^m w_i,w_i)\mod p$$

因为 $p$ 不一定是质数，所以直接上 $\text{exLucas}$ 就行了。

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline ll read()
{
    char ch=getchar();
    ll f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

ll p,zs[100005],cnt,w[10];
bool ss[100005];

inline void get_prime()
{
    memset(ss,1,sizeof(ss));
    ss[0]=ss[1]=0;
    ll sqn=sqrt(p);
    for (ll i=2;i<=sqn;i++)
    {
        if (ss[i]) zs[++cnt]=i;
        for (ll j=1;j<=cnt && zs[j]*i<=sqn;j++)
        {
            ss[zs[j]*i]=0;
            if (i%zs[j]==0) break;
        }
    }
}

ll exgcd(ll l,ll r,ll &x,ll &y)
{
    if (r==0)
    {
        x=1; y=0;
        return l;
    }
    ll ans=exgcd(r,l%r,y,x);
    y-=l/r*x;
    return ans;
}

inline ll qpow(ll x,ll y,ll ha)
{
    ll ans=1;
    while (y)
    {
        if (y&1) ans=ans*x%ha;
        y>>=1;
        x=x*x%ha;
    }
    return ans%ha;
}

inline ll inv(ll now,ll ha)
{
    ll x=0,y=0;
    exgcd(now,ha,x,y);
    return (x%ha+ha)%ha;
}

inline ll fac(ll x,ll pi,ll pk)
{
    if (!x) return 1;
    ll ans=1;
    for (ll i=2;i<=pk;i++)
    {
        if (i%pi==0) continue;
        ans=ans*i%pk;
    }
    ans=qpow(ans,x/pk,pk);
    ll len=x%pk;
    for (ll i=2;i<=len;i++)
    {
        if (i%pi==0) continue;
        ans=ans*i%pk;
    }
    return ans*fac(x/pi,pi,pk)%pk;
}

inline ll C(ll n,ll m,ll pi,ll pk)
{
    ll s=0;
    for (ll i=n;i;i/=pi) s+=i/pi;
    for (ll i=m;i;i/=pi) s-=i/pi;
    for (ll i=n-m;i;i/=pi) s-=i/pi;
    return fac(n,pi,pk)*inv(fac(m,pi,pk),pk)%pk*inv(fac(n-m,pi,pk),pk)%pk*qpow(pi,s,pk)%pk;
}

inline ll exlucas(ll n,ll m)
{
    ll ans=0,p2=p;
    for (ll i=1;i<=cnt;i++)
    {
        if (p2%zs[i]) continue;
        ll pk=1;
        while (p2%zs[i]==0) p2/=zs[i],pk*=zs[i];
        ll ai=C(n,m,zs[i],pk),mi=p/pk;
        ans=(ans+ai*mi%p*inv(mi,pk)%p)%p;
    }
    if (p2>1)
    {
        ll ai=C(n,m,p2,p2),mi=p/p2;
        ans=(ans+ai*mi%p*inv(mi,p2)%p)%p;
    }
    return ans;
}

signed main()
{
    p=read();
    get_prime();
    ll n,m;
    n=read(); m=read();
    ll w_sum=0;
    for (ll i=1;i<=m;i++) w[i]=read(),w_sum+=w[i];
    if (w_sum>n) return !printf("Impossible");
    ll ans=1;
    for (int i=1;i<=m;i++)
    {
        ans=ans*exlucas(n,w[i])%p;
        n-=w[i];
    }
    return !printf("%lld",ans);
}