Luogu

BZOJ

分析

这题最多是紫题吧,式子我都能想出来qwq

前置姿势:扩展Lucas

首先可以推出答案为$\large C_{n}^{w_1}\times C_{n-w_1}^{w_2}\times... \mod P$

组合意义很明确,就是在剩下的礼物中选出$w_i$个的方案数,再根据乘法原理乘起来。

显然我们要每步都对算出的组合数取模,但是这里的$P$不一定是质数,所以直接上$\text{扩展Lucas}$即可。

细节见代码。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef int mainint;
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

int n,m,p,w[6];

inline int exgcd(int a,int b,int& x,int& y) {
    if (!b) { x=1,y=0; return a; }
    int d=exgcd(b,a%b,x,y);
    int z=x; x=y; y=z-(a/b)*y;
    return d;
}

inline int FastPow(int a,int b,int m) {
    int ans=1;
    for (;b;b>>=1,a=a*a%m)
        if (b&1) ans=ans*a%m;
    return ans;
}

inline int fact(int n,int pi,int pk) {
    if (!n) return 1;
    int ans=1;
    for (re int i=2;i<=pk;++i)
        if (i%pi) ans=ans*i%pk;
    ans=FastPow(ans,n/pk,pk);
    for (re int i=2;i<=n%pk;++i)
        if (i%pi) ans=ans*i%pk;
    return ans*fact(n/pi,pi,pk)%pk;
}

inline int getInv(int n,int m) {
    int x,y; exgcd(n,m,x,y);
    return x>0?x:x+m;
}

inline int CRT(int b,int m) { return b*getInv(p/m,m)%p*(p/m)%p; }

inline int C(int n,int m,int pi,int pk) {
    int d1=fact(n,pi,pk),d2=fact(m,pi,pk),d3=fact(n-m,pi,pk);
    int k=0;
    for (re int i=n;i;i/=pi) k+=i/pi;
    for (re int i=m;i;i/=pi) k-=i/pi;
    for (re int i=n-m;i;i/=pi) k-=i/pi;
    return d1*getInv(d2,pk)%pk*getInv(d3,pk)%pk*FastPow(pi,k,pk)%pk;
}

inline int EX_Lucas(int n,int m) {
    int ans=0,tmp=p,pk;
    int end=sqrt(p);
    for (re int i=2;i<=end;++i) {
        if (tmp%i==0) {
            pk=1; while (tmp%i==0) pk*=i,tmp/=i;
            ans=(ans+CRT(C(n,m,i,pk),pk))%p;
        }
    }
    if (tmp>1) ans=(ans+CRT(C(n,m,tmp,tmp),tmp))%p;
    return ans;
}

mainint main() {
    p=read(),n=read(),m=read(); int s=0;
    for (re int i=1;i<=m;++i) s+=(w[i]=read());
    if (s>n) { puts("Impossible"); return 0; }
    int ans=1;
    for (re int i=1;i<=m;++i)
        ans=ans*EX_Lucas(n,w[i])%p,n-=w[i];
    printf("%lld\n",ans);
    return 0;
}
最后修改:2019 年 09 月 29 日 07 : 57 AM