题解 P2183 【[国家集训队]礼物】
Biscuit46
2019-01-23 07:59:24
## 传送门
[BZOJ](https://www.lydsy.com/JudgeOnline/problem.php?id=2142)
[洛谷](https://www.luogu.org/problemnew/show/P2183)
## Solution
大家在写本题之前需要先了解[exLucas(当然和Lucas没有任何关系啊!)](http://pmycqacf.ml/index.php/archives/lucas-exlucas.html)
考虑一下方案数怎么算,不就是直接组合数一段乱搞就可以了?
$C_n^{w_1}*C_{n-w_1}^{w_2}*C_{n-w_1-w_2}^{w_3}*...*C_{n-w_1-w_2-...-w_{m-1}}^{w_m}$
然后就是exLucas裸题了.
```cpp
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define ll long long
#define re register
#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
inline int gi(){
int f=1,sum=0;char ch=getchar();
while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
return f*sum;
}
ll num,number[50010],r[50010],prime[50010];
ll qpow(ll a,ll b,ll mod){
ll ret=1;
while(b){
if(b&1)ret=(ret*a)%mod;
b>>=1;a=(a*a)%mod;
}
return ret;
}
ll exgcd(ll a,ll b,ll&x,ll&y){
if(!b){
x=1;y=0;
return a;
}
ll d=exgcd(b,a%b,y,x);y-=a/b*x;
return d;
}
ll inv(ll a,ll b){
ll x,y;
ll d=exgcd(a,b,x,y);
return (x+b)%b;
}
ll crt(){
ll M=1,ret=0;
for(int i=1;i<=num;i++)M*=number[i];
for(int i=1;i<=num;i++){
ll m=M/number[i];
ret=(ret+m*inv(m,number[i])*r[i])%M;
}
return ret;
}
ll multi(ll n,ll pi,ll pk){
if(!n)return 1;
ll ans=1;
for(ll i=2;i<=pk;i++)if(i%pi)ans=ans*i%pk;
ans=qpow(ans,n/pk,pk);
for(ll i=2;i<=n%pk;i++)if(i%pi)ans=ans*i%pk;
return ans*multi(n/pi,pi,pk)%pk;
}
ll exlucas(ll n,ll m,ll pi,ll pk){
if(m>n)return 0;
ll a=multi(n,pi,pk),b=multi(m,pi,pk),c=multi(n-m,pi,pk);
ll k=0;
for(ll i=n;i;i/=pi)k+=i/pi;
for(ll i=m;i;i/=pi)k-=i/pi;
for(ll i=n-m;i;i/=pi)k-=i/pi;
return a*inv(b,pk)%pk*inv(c,pk)%pk*qpow(pi,k,pk)%pk;
}
ll exall(ll n,ll m,ll p){
for(int i=1;i<=num;i++)r[i]=exlucas(n,m,prime[i],number[i]);
return crt();
}
void fz(ll n){
num=0;
for(ll i=2;i*i<=n;i++){
if(n%i==0){
ll pk=1;
while(n%i==0)pk*=i,n/=i;
++num;
number[num]=pk;
prime[num]=i;
}
}
if(n>1){++num;number[num]=n;prime[num]=n;}
}
ll n,m,p,w[10],sum;
signed main(){
p=gi();
n=gi();m=gi();
for(int i=1;i<=m;i++){
w[i]=gi();sum+=w[i];
}
if(sum>n)return puts("Impossible"),0;
fz(p);
ll ans=1;
for(int i=1;i<=m;i++){
n-=w[i-1];
ans=(ans*exall(n,w[i],p))%p;
}
printf("%lld\n",ans);
return 0;
}
```