Luogu

LOJ

分析

考虑容斥，求出至少 $i$ 个人被 D 神碾压的方案数 $f_i$。

首先钦定 $i$ 个人被 D 神碾压，然后对于每一科选出没有被 D 神碾压但是这一科分数比他低的 $n-r_i-i$ 个人，然后再枚举 D 神的分数并计算出其它人分数的方案数，即可求出 $f_i$，即
$$
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}
$$
直接计算显然复杂度爆炸。考虑先对于每个 $i$ 求出 $\sum$ 后式子的值 $s_i$
$$
\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$ 为自然数幂和的形式，因此可以拉格朗日插值。

最后根据容斥原理不难得到答案
$$
\sum_{i=k}^{n-1}(-1)^{i-k}{i\choose k}f_i
$$
总时间复杂度为 $\mathcal{O}(n^2m)$。

代码

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

int read() {
    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() {
    n=read(),m=read(),k=read();
    for (int i=1;i<=m;++i) u[i]=read();
    for (int i=1;i<=m;++i) r[i]=read();
    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;
}