2020-05-17 17:30:34

$$f_i={n\choose i}\prod_{i=1}^m{n-i-1\choose n-r_i-i}\sum_{j=1}^{u_i}j^{n-r_i}(u_i-j)^{r_i-1}$$

\begin{aligned}s_i&=\sum_{j=1}^{u_i}j^{n-r_i}(u_i-j)^{r_i-1}\\&=\sum_{j=1}^{u_i}j^{n-r_i}\sum_{l=0}^{r_i-1}{r_i-1\choose l}{u_i}^{r_i-1-l}(-j)^{l}\\&=\sum_{l=0}^{r_i-1}(-1)^l{r_i-1\choose l}{u_i}^{r_i-1-l}\sum_{j=1}^{u_i}j^{n-r_i+l}\end{aligned}

$$\sum_{i=k}^{n-1}(-1)^{i-k}{i\choose k}f_i$$

// ===================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

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;
}

const int N=100+10;
const int mod=1e9+7;
int qpow(int a,int b) { int c=1;
for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
return c;
}

int n,m,k,u[N],r[N];
int fac[N],ifac[N];
int s[N],f[N*100];

int C(int n,int m) {
return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}

int calc(int d,int n) {
if (d<=n) return f[d];
int o=(n&1)?-1:1,tmp=1,ans=0;
for (int i=1;i<=n;++i) tmp=1ll*tmp*(d-i)%mod;
for (int i=1;i<=n;++i) tmp=1ll*tmp*qpow(i,mod-2)%mod;
for (int i=0;i<=n;++i,o=-o) {
ans=(ans+1ll*o*f[i]%mod*tmp)%mod;
tmp=1ll*tmp*(d-i)%mod*qpow(d-i-1,mod-2)%mod;
tmp=1ll*tmp*(n-i)%mod*qpow(i+1,mod-2)%mod;
}
return (ans+mod)%mod;
}

int main() {
fac[0]=1;
for (int i=1;i<=n;++i) fac[i]=1ll*fac[i-1]*i%mod;
ifac[n]=qpow(fac[n],mod-2);
for (int i=n;i;--i) ifac[i-1]=1ll*ifac[i]*i%mod;
for (int i=1;i<=m;++i)
for (int l=0;l<r[i];++l) {
int lim=n-r[i]+l+2;
for (int j=1;j<=lim;++j) f[j]=(f[j-1]+qpow(j,n-r[i]+l))%mod;
int res=1ll*C(r[i]-1,l)*qpow(u[i],r[i]-l-1)%mod*calc(u[i],lim)%mod;
if (l&1) s[i]=(s[i]-res+mod)%mod;
else s[i]=(s[i]+res)%mod;
}
int ans=0;
for (int i=k;i<n;++i) {
int res=1ll*C(n-1,i)*C(i,k)%mod;
for (int j=1;j<=m;++j)
res=1ll*res*C(n-i-1,n-r[j]-i)%mod*s[j]%mod;
if ((i-k)&1) ans=(ans-res+mod)%mod;
else ans=(ans+res)%mod;
}
printf("%d\n",ans);
return 0;
}
• star
首页