1.分特产:
首先考虑分设 \(f_i\) 与 \(g_i\) 分别表示钦定与恰好,由题意我们容易知道 \(f_i\) 首先应钦定 \(i\) 个人,方案为 \(\binom{n}{i}\),然后对剩下的 \(n-i\) 个人插 \(a_j\) 个板,有 \(\binom{a_j+n-i-1}{a_j}\) 种方案数,因此有 $$f_i=\binom{n}{i}+\prod_{j=1}^n\binom{a_j+n-i-1}{a_j}$$然后我们只需要根据二项式反演推出 \(g_i\) 来即可。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int p=1e9+7;
int n,m,ans(0);
int a[100000],fac[500000],F[2000],G[2000];
int qpow(int a,int b){
int res(1);
for(;b;a=(a*a)%p,b>>=1) if(b&1) res=(res*a)%p;
return res%p;
}
// int cc(int n,int m){return (m>n)?0:fac[n]*qpow(fac[n-m],p-2)%p*qpow(fac[m],p-2)%p;}
// int C(int n,int m){return !m?1:cc(n%p,m%p)%p*C(n/p,m/p)%p;}
int cc(int n,int m){return (m>n)?0:((fac[n]*qpow(fac[m],p-2))%p*qpow(fac[n-m],p-2)%p);}
int C(int n,int m){return !m?1:cc(n%p,m%p)*C(n/p,m/p)%p;}
signed main(){
fac[0]=1;
for(int i=1;i<=350000;++i) fac[i]=fac[i-1]*i%p;
scanf("%lld %lld",&n,&m);
for(int i=1;i<=m;++i) scanf("%lld",&a[i]);
int tem(1);
for(int i=0;i<n;++i){
tem=1;
for(int j=1;j<=m;++j) tem=tem*C(a[j]+n-i-1,n-i-1)%p;
F[i]=C(n,i)*tem%p;
}
for(int i=0;i<n;++i){
if(i&1) ans=(ans-F[i])%p;
else ans=(ans+F[i])%p;
}
printf("%lld",ans);
}