新修缮的代码:
```cpp
#include<bits/stdc++.h>
using namespace std;
const long long M=10,N=25;
namespace exLucas {
long long MOD,n,m,sum,ans,w[M];
long long a[N],b[N];
void exgcd(long long x,long long y,long long &sum1,long long &sum2) {
if(!y) {
sum1=1,sum2=0;
return;
}
exgcd(y,x%y,sum1,sum2);
long long X=sum1;
sum1=sum2;
sum2=X-x/y*sum2;
}
long long inv(long long x,long long mod) {
long long res=0,y=0;
exgcd(x,mod,res,y);
return (res+mod)%mod;
}
long long crt(long long n) {
long long res=0;
for(long long i=1; i<=n; i++) {
long long mi=MOD/a[i],pi=inv(mi,a[i]);
res=(res+(b[i]*(mi*pi)%MOD)%MOD)%MOD;
}
return res;
}
long long ksm(long long x,long long y,long long mod) {
long long res=1;
while(y) {
if(y&1) res=(res*x)%mod;
x=(x*x)%mod;
y>>=1;
}
return res;
}
long long fac(long long n,long long mod,long long a) {
if(!n) return 1;
long long xhj=1,yushu=1;
for(long long i=1; i<=a; i++)
if(i%mod!=0)
xhj=(xhj*i)%mod;
xhj=ksm(xhj,n/a,a);
for(long long i=a*(n/a); i<=n; i++)
if(i%mod!=0)
yushu=(yushu*(i%a))%a;
return ((fac(n/mod,mod,a)*xhj)%a*yushu)%a;
}
long long sfac(long long n,long long p) {
return n<p?0:sfac(n/p,p)+(n/p);
}
long long C(long long n,long long m,long long p,long long mod) {
long long a1=fac(n,p,mod)%mod,a2=inv(fac(m,p,mod),mod)%mod,a3=inv(fac(n-m,p,mod),mod)%mod,a4=ksm(p,sfac(n,p)-sfac(m,p)-sfac(n-m,p),mod)%mod;
return (((a1*a2)%mod*a3)%mod*a4)%mod;
}
long long exlucas(long long n,long long m,long long mod) {
long long p=mod,cnt=0;
for(long long i=2; i*i<=mod; i++) {
if(p%i==0) {
long long num=1;
while(p%i==0) {
num*=i;
p/=i;
}
a[++cnt]=num;
b[cnt]=C(n,m,i,num);
}
}
if(p>1) {
a[++cnt]=p;
b[cnt]=C(n,m,p,p);
}
return crt(cnt);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>MOD;
cin>>n>>m;
for(long long i=1; i<=m; i++) cin>>w[i];
for(long long i=1; i<=m; i++) sum+=w[i];
if(sum>n) {
cout<<"Impossible";
return 0;
}
ans=exlucas(n,sum,MOD)%MOD;
for(long long i=1; i<m; i++) {
ans=(ans*exlucas(sum,w[i],MOD))%MOD;
sum-=w[i];
}
cout<<ans%MOD;
}
}
int main() {
return exLucas::main();
}
```
by 快乐的大童 @ 2022-07-20 11:24:44