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

题目描述

一年一度的圣诞节快要来到了。每年的圣诞节小E都会收到许多礼物，当然他也会送出许多礼物。不同的人物在小E心目中的重要性不同，在小E心中分量越重的人，收到的礼物会越多。小E从商店中购买了n件礼物，打算送给m个人，其中送给第i个人礼物数量为wi。请你帮忙计算出送礼物的方案数（两个方案被认为是不同的，当且仅当存在某个人在这两种方案中收到的礼物不同）。由于方案数可能会很大，你只需要输出模P后的结果。

输入格式

输入的第一行包含一个正整数P，表示模；

第二行包含两个整整数n和m，分别表示小E从商店购买的礼物数和接受礼物的人数；

以下m行每行仅包含一个正整数wi，表示小E要送给第i个人的礼物数量。

输出格式

若不存在可行方案，则输出“Impossible”，否则输出一个整数，表示模P后的方案数。

输入输出样例

输入 #1

100

4 2

1

2

输出 #1

12

输入 #2

100

2 2

1

2

输出 #2

Impossible

说明/提示

【样例说明】

下面是对样例1的说明。

以“/”分割，“/”前后分别表示送给第一个人和第二个人的礼物编号。12种方案详情如下：

1/23 1/24 1/34

2/13 2/14 2/34

3/12 3/14 3/24

4/12 4/13 4/23

设 P = p 1 c 1 ∗ p 2 c 2 ∗ p 3 c 3 . . . p t c t , p i P={p_1}^{c_1}*{p_2}^{c_2}*{p_3}^{c_3} ... {p_t} ^ {c_t},{p_i} P=p1​c1​∗p2​c2​∗p3​c3​...pt​ct​,pi​为质数。

对于 100 100% 100的数据， 1 ≤ n ≤ 1 0 9 ， 1 ≤ m ≤ 5 ， 1 ≤ p i c i ≤ 1 0 5 ， 1 ≤ P ≤ 1 0 9 。 1≤n≤10^9，1≤m≤5，1≤pi^ci≤10^5，1≤P≤10^9。 1≤n≤109，1≤m≤5，1≤pici≤105，1≤P≤109。

解释：ans= C n a 1 ∗ C n − a 1 a 2 ∗ C n − a 1 − a 2 a 3 . . . ∗ C n − a 1 − a 2 − . . . a m − 1 a m C_n^{a_1}*C_{n-a_1}^{a_2}*C_{n-a_1-a_2}^{a_3}...*C_{n-a_1-a_2-...a_{m-1}}^{a_m} Cna1​​∗Cn−a1​a2​​∗Cn−a1​−a2​a3​​...∗Cn−a1​−a2​−...am−1​am​​

那么我可以利用中国剩余定理和扩展卢卡斯定理去解决…然后就完事了…

#include<iostream>
#include<cstring>
using namespace std;
long long P=0,n=0,m=0;
long long s[10]={0};
long long sum=0;
long long ai[103]={0},bi[103]={0};
long long fact[100003]={1,1};
long long x=0,y=0;
void init(long long p){
    for(int i=2;i<=1e5;i++) fact[i]=fact[i-1]*i%p;
}
long long pow(long long y,long long z,long long p){
    y%=p;long long ans=1;
    for(int i=z;i;i>>=1,y=y*y%p)if(i&1)ans=ans*y%p;
    return ans;
}
long long C(long long n,long long m,long long p){
    if(m>n)return 0;
    return ((fact[n]*pow(fact[m],p-2,p))%p*pow(fact[n-m],p-2,p)%p);
}
long long Lucas(long long n,long long m,long long p){
    if(!m)return 1;
    return C(n%p,m%p,p)*Lucas(n/p,m/p,p)%p;
}
long long mul(long long a,long long b,long long mod){
    long long res=0;
    while(b>0){
        if(b&1) res=(res+a)%mod;
        a=(a+a)%mod;
        b>>=1;
    }
    return res;
}
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 gcd=exgcd(b,a%b,x,y);
    long long tp=x;
    x=y; y=tp-a/b*y;
    return gcd;
}
long long excrt(int n){
    long long x,y;
    long long M=bi[1],ans=ai[1];
    for(int i=2;i<=n;i++){
        long long a=M,b=bi[i],c=(ai[i]-ans%b+b)%b;
        long long gcd=exgcd(a,b,x,y),bg=b/gcd;
        if(c%gcd!=0) return -1;
        x=mul(x,c/gcd,bg);
        ans+=x*M;
        M*=bg;
        ans=(ans%M+M)%M;
    }
    return (ans%M+M)%M;
}
long long gcd(long long a,long long b){
    if (b==0) return a;
    return gcd(b,a%b);
}
long long INV(long long a,long long p){
    long long x,y;
    exgcd(a,p,x,y);
    return (x+p)%p;
}
long long lcm(long long a,long long b){
    return a/gcd(a,b)*b;
}
long long mabs(long long x){
    return (x>0?x:-x);
}
long long F(long long n,long long P,long long PK){
    if (n==0) return 1;
    long long rou=1;//循环节
    long long rem=1;//余项
    for (long long i=1;i<=PK;i++){
        if (i%P) rou=rou*i%PK;
    }
    rou=pow(rou,n/PK,PK);
    for (long long i=PK*(n/PK);i<=n;i++){
        if (i%P) rem=rem*(i%PK)%PK;
    }
    return F(n/P,P,PK)*rou%PK*rem%PK;
}
long long G(long long n,long long P){
    if (n<P) return 0;
    return G(n/P,P)+(n/P);
}
long long C_PK(long long n,long long m,long long P,long long PK){
    long long fz=F(n,P,PK),fm1=INV(F(m,P,PK),PK),fm2=INV(F(n-m,P,PK),PK);
    long long mi=pow(P,G(n,P)-G(m,P)-G(n-m,P),PK);
    return fz*fm1%PK*fm2%PK*mi%PK;
}
long long A[1001],B[1001];
long long exLucas(long long n,long long m,long long P){
    long long ljc=P,tot=0;
    for (long long tmp=2;tmp*tmp<=P;tmp++){
        if (!(ljc%tmp)){
            long long PK=1;
            while (!(ljc%tmp)){
                PK*=tmp;ljc/=tmp;
            }
            A[++tot]=PK;B[tot]=C_PK(n,m,tmp,PK);
        }
    }
    if (ljc!=1){
        A[++tot]=ljc;B[tot]=C_PK(n,m,ljc,ljc);
    }
    long long ans=0;
    for (long long i=1;i<=tot;i++){
        long long M=P/A[i],T=INV(M,A[i]);
        ans=(ans+B[i]*M%P*T%P)%P;
    }
    return ans;
}
long long mk(long long n,long long m,long long P){
    int t=0;
    for(int i=2;i*i<=P;i++){
        if(P%i==0){
            bi[++t]=1;
            while(P%i==0){
                bi[t]*=i;
                P/=i;
            }
        }
    }
    if(P!=1) bi[++t]=P;
    for(int i=1;i<=t;i++){
        init(bi[i]);
        ai[i]=exLucas(n,m,bi[i]);
    }
    return excrt(t);
}
int main(){
    ios::sync_with_stdio(false);
    cin>>P;
    cin>>n>>m;
    for(int i=1;i<=m;i++) cin>>s[i],sum+=s[i];
    if(sum>n){
        cout<<"Impossible"<<endl;
        return 0;
    }
    long long ret=1;
    sum=0;
    for(int i=1;i<=m;i++){
        long long temp=mk(n-sum,s[i],P);
        ret*=temp;sum+=s[i];
        ret%=P;
    }
    cout<<ret<<endl;
    return 0;
}