P3270

· · 题解

是我会的题，所以感觉难度不如 noip T3T4。

设 f_{i,j} 表示考虑到前 i 门课，有 j 人被 B 碾压。

转移，设这轮中有 k 个原本被碾压的人不再被碾压，则相当于从 f_{i-1,j+k} 转移到 f_{i,j}。考虑转移系数，首先是 j+k 人中选 k 人，现在排名在 B 前面的位置还有 r_i-1-k 位，所以从 n-1-j-k 中选 r_i-1-k 个。最后是每个人有一个分数，易得要乘上 \sum_{j=1}^{u_i}j^{n-r_i}(u_i-j)^{r_i-1}。所以转移方程为：

f_{i,j} = \sum_{k=0}^{\min(n-j-1,r_i-1)}f_{i-1,j+k}\dbinom{j+k}k\dbinom{n-1-j-k}{r_i-1-k}T_i

其中：

T_i = \sum_{j=1}^{u_i}j^{n-r_i}(u_i-j)^{r_i-1}

边界是 f_{0,n-1}=1，答案取 f_{m,k}。

容易发现瓶颈在于 T_i 的计算，看到这个式子我们想到了 CF622F，于是直接拉格朗日插值就能求出来了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 110;
const ll P = 1e9 + 7;
int n, m, k, u[N], r[N];
ll f[N][N], y[N*2], t[N], C[N][N];

ll qp(ll x, ll y){
    ll ans = 1;
    while(y){
        if(y & 1){
            ans = ans * x % P;
        }
        x = x * x % P;
        y >>= 1;
    }
    return ans;
}

ll lglr(int xk){
    ll res = 0;
    for(int i = 1; i <= n + n; ++ i){
        ll mul = y[i];
        for(int j = 1; j <= n + n; ++ j){
            if(j != i){
                mul = mul * (xk - j + P) % P * qp(i-j+P, P-2) % P;
            }
        }
        res = (res + mul) % P;
    }
    return res;
}

int main(){
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 1; i <= m; ++ i){
        scanf("%d", &u[i]);
    }
    for(int i = 1; i <= m; ++ i){
        scanf("%d", &r[i]);
    }
    C[0][0] = 1;
    for(int i = 1; i <= n; ++ i){
        C[i][0] = C[i][i] = 1;
        for(int j = 1; j < i; ++ j){
            C[i][j] = (C[i-1][j] + C[i-1][j-1]) % P;
        }
    }
    f[0][n-1] = 1;
    for(int i = 1; i <= m; ++ i){
        for(int j = 1; j <= n + n; ++ j){
            y[j] = (y[j-1] + qp(j, n-r[i]) * qp(u[i]-j, r[i]-1)) % P;
        }
        t[i] = lglr(u[i]);
        for(int j = 0; j <= n-1; ++ j){
            for(int k = 0; k <= min(n-j-1, r[i]-1); ++ k){
                f[i][j] = (f[i][j] + f[i-1][j+k] * C[j+k][k] % P * C[n-1-j-k][r[i]-1-k] % P * t[i] % P) % P;
            }
        }
    }
    printf("%lld\n", f[m][k]);
    return 0;
}