题目描述

题目链接

太长了 不会描述。

接下来假定 $m$ 和 $n$ 同阶。

题解

我们设 $f_n$ 表示恰好有 $n$ 个人被碾压的方案数，显然 $f_k$ 即为所求。

发现这个恰好不是很好限定 如果直接组合数选我们不太好强制规定哪些人不被碾压 于是我们考虑设 $g_n$ 表示至少有 $n$ 个人被碾压的方案数，一种计算方法就是枚举真实被碾压的方案数，然后选出来我们认为的被碾压的人是谁即可。二项式反演可以得到想要的答案。

$$ \begin{aligned} g_k = \sum_{i=k}^N \binom i k f_i\\ \Rightarrow f_k = \sum_{i=k}^N (-1)^{i-k} \binom i k g_i \end{aligned} $$

任务转化为求 $g$。

先列出朴素的式子：

$$ \begin{aligned} g_k = \binom {N-1} {k} \prod_{i=1}^M \binom{N-k-1}{N-r_i-k}\sum_{j=1}^{U_i} j^{N-r_i}(U_i-j)^{r_i-1} \end{aligned} $$

就是首先选出来被钦定碾压的那些人 然后考虑处理剩下的每一门课的情况 每课都会有 $N-r_i-k$ 个剩下的比 B 神得分少的 所以需要从没有被钦定碾压的 $N-k-1$ 个人中选出来。最后需要去枚举 B 神得了多少分 分别计算即可。

不妨发现后面的式子只和 $i$ 有关 我们设其为 $h_i$ 并进行化简：

$$ \begin{aligned} h_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_{k=0}^{r_i-1}U_i^{k}j^{r_i-1-k}(-1)^{r_i-1-k}\\&= \sum_{k=0}^{r_i-1}(-1)^{r_i-k-1}U_i^k\sum_{j=1}^{U_i}j^{N-k-1} \end{aligned} $$

我们发现后面的式子是 $\sum_{i=1}^n i^m$ 的形式 可以用拉格朗日插值做到 $O(n)$

于是我们去枚举计算所有的 $h$ 时间复杂度是 $O(n^3)$

接下来去枚举计算所有的 $g$ 时间复杂度是 $O(n^2)$

计算单个 $f$ 就只需要 $O(n)$ 了。所以总复杂度是 $O(n^3)$。

#include<bits/stdc++.h>

#define fi first
#define se second
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int ha = 1e9 + 7;
const int MAXN = 1e5 + 5;

int fac[MAXN],inv[MAXN],n,m,k,U[MAXN];

inline int qpow(int a,int n=ha-2){
    int res = 1;
    while(n){
        if(n & 1) res = 1ll*res*a%ha;
        a = 1ll*a*a%ha;
        n >>= 1;
    }
    return res;
}

inline void prework(){
    fac[0] = 1;FOR(i,1,MAXN-1) fac[i] = 1ll*fac[i-1]*i%ha;
    inv[MAXN-1] = qpow(fac[MAXN-1]);
    ROF(i,MAXN-2,0) inv[i] = 1ll*inv[i+1]*(i+1)%ha;
}

int y[MAXN];
inline int cha(int n,int m){// [1..n]^m
    int up = 1,ans = 0;
    FOR(i,1,m+1) y[i] = (y[i-1]+qpow(i,m))%ha;
    if(n <= m+1) return y[n];
    FOR(i,0,m+1) up = 1ll*up*(n-i+ha)%ha;
    FOR(i,0,m+1){
        int t = 1ll*up*qpow((n-i+ha)%ha)%ha;
        t = 1ll*t*inv[i]%ha*inv[m+1-i]%ha;
        if((m+1-i)&1) t = (ha-t);
        (ans += 1ll*t*y[i]%ha) %= ha;
    }
    return ans;
}

inline int C(int n,int m){
    if(n < m) return 0;
    if(m < 0) return 0;
    return 1ll*fac[n]*inv[m]%ha*inv[n-m]%ha;
}

int h[MAXN],r[MAXN],g[MAXN];

int main(){
    prework();
    scanf("%d%d%d",&n,&m,&k);
    FOR(i,1,m) scanf("%d",U+i);
    FOR(i,1,m) scanf("%d",r+i);
    FOR(i,1,m){
//        int chk = 0;
//        FOR(j,1,U[i]){
//            (chk += 1ll*qpow(j,n-r[i])*qpow(U[i]-j,r[i]-1)%ha) %= ha;
//        }
        FOR(k,0,r[i]-1){
            int t = 1ll*C(r[i]-1,k)*qpow(U[i],k)%ha*cha(U[i],n-k-1)%ha;
            if((r[i]-k-1)&1) t = ha-t;
            (h[i] += t) %= ha;
        }
//        DEBUG(h[i]);DEBUG(chk);
//        assert(h[i]==chk);
    }
    FOR(i,1,n){
        g[i] = C(n-1,i);
        FOR(j,1,m){
            g[i] = 1ll*g[i]*h[j]%ha*C(n-i-1,n-i-r[j])%ha;
        }
    }
    int ans = 0;
    FOR(i,k,n){
        int t = 1ll*C(i,k)*g[i]%ha;
        if((i-k)&1) t = ha-t;
        (ans += t) %= ha;
    }
    printf("%d\n",ans);
    return 0;
}