好吧学长说是板子。。。学了之后才发现就是板子qwq
题意：求$ C_n^{w_1}*C_{n-w_1}^{w_2}*C_{n-w_1-w_2}^{w_3}*...\space mod \space P$
当然，如果$\Sigma w_i >n$,则无解。
（不会扩展卢卡斯？）
#include<cstdio>
#include<iostream>
#define ll long long
#define R register ll
using namespace std;
inline ll g() {
R ret=,fix=; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-:fix;
do ret=ret*+(ch^); while(isdigit(ch=getchar())); return ret*fix;
}
inline ll qpow(ll a,ll b,ll p) { R ret=; a%=p;
for(;b;b>>=,(a*=a)%=p) if(b&) (ret*=a)%=p; return ret;
}
inline void exgcd(ll a,ll b,ll& x,ll& y) {
if(!b) {x=,y=; return ;}
exgcd(b,a%b,y,x),y-=a/b*x;
}
inline ll Inv(ll n,ll p) {
R x,y; exgcd(n,p,x,y); return (x%p+p)%p;
}
ll n,m,p,w[];
inline ll fac(int n,int pi,int pk) {
if(!n) return ; R ans=;
for(R i=;i<pk;++i) if(i%pi) ans=ans*i%pk;//循环节
ans=qpow(ans,n/pk,pk); //快速幂，即循环节的个数
for(R i=;i<=n%pk;++i) if(i%pi) ans=ans*i%pk;//处理最后的散块
return ans*fac(n/pi,pi,pk)%pk; //递归求解
}
inline ll L(int n,int m,int pi,int pk) {
R ind=; for(R i=n;i;i/=pi) ind+=i/pi;
for(R i=m;i;i/=pi) ind-=i/pi;
for(R i=n-m;i;i/=pi) ind-=i/pi;
R N=fac(n,pi,pk),M=fac(m,pi,pk),N_M=fac(n-m,pi,pk);
return N*Inv(M,pk)%pk*Inv(N_M,pk)%pk*qpow(pi,ind,pk)%pk;
}
inline ll solve(int n,int m) { R tmp=p,ans=;
for(R i=;i*i<=tmp;++i) if(tmp%i==) {
R pk=; while(tmp%i==) pk*=i,tmp/=i;
ans=(ans+L(n,m,i,pk)*Inv(p/pk,pk)%p*p/pk%p)%p;
} if(tmp>) ans=(ans+L(n,m,tmp,tmp)*Inv(p/tmp,tmp)%p*p/tmp%p)%p;
return ans;
}
signed main() {
p=g(),n=g(),m=g(); R sum=;
for(R i=;i<=m;++i) sum+=(w[i]=g());
if(sum>n) {printf("Impossible\n"); return ;}
R ans=; for(R i=;i<=m;++i) ans=ans*solve(n,w[i])%p,n-=w[i];
printf("%lld\n",ans);
}
2019.05.18