题目地址：洛谷：【P3270】[JLOI2016]成绩比较 – 洛谷、BZOJ：Problem 4559. — [JLoi2016]成绩比较

题目描述

G系共有n位同学，M门必修课。这N位同学的编号为0到N-1的整数，其中B神的编号为0号。这M门必修课编号为0到M-1的整数。一位同学在必修课上可以获得的分数是1到Ui中的一个整数。
如果在每门课上A获得的成绩均小于等于B获得的成绩，则称A被B碾压。在B神的说法中，G系共有K位同学被他碾压（不包括他自己），而其他N-K-1位同学则没有被他碾压。D神查到了B神每门必修课的排名。
这里的排名是指：如果B神某门课的排名为R，则表示有且仅有R-1位同学这门课的分数大于B神的分数，有且仅有N-R位同学这门课的分数小于等于B神（不包括他自己）。
我们需要求出全系所有同学每门必修课得分的情况数，使其既能满足B神的说法，也能符合D神查到的排名。这里两种情况不同当且仅当有任意一位同学在任意一门课上获得的分数不同。
你不需要像D神那么厉害，你只需要计算出情况数模10^9+7的余数就可以了。

输入输出格式

输入格式：
第一行包含三个正整数N,M,K，分别表示G系的同学数量（包括B神），必修课的数量和被B神碾压的同学数量。第二行包含M个正整数，依次表示每门课的最高分Ui。第三行包含M个正整数，依次表示B神在每门课上的排名Ri。保证1<=Ri<=N。数据保证至少有1种情况使得B神说的话成立。

输出格式：
仅一行一个正整数，表示满足条件的情况数模10^9+7的余数。

输入输出样例

输入样例#1：

3 2 1
2 2
1 2

输出样例#1：

10

说明

N<=100,M<=100,Ui<=10^9

题解

本题需要的数学姿势：拉格朗日插值法及其应用 | KSkun’s Blog
参考资料：4559: [JLoi2016]成绩比较 – CSDN博客
计数问题，分层考虑。我们令dp[i][j]表示当前枚举到第i门课，被B神碾压的同学数为j的方案数，考虑转移中从j大的向j小的转移，即
dp[i][j] = \sum_{k=j}^n dp[i-1][k] \cdot \mathrm{C}_{k}^{k-j} \cdot \mathrm{C}_{n-k}^{R_i - 1 - (k-j)} \cdot d_i
组合系数的含义是，计算之前科目被碾压但该科没被碾压的学生方案数及其他该科不低于B神的学生方案数。后面的d_i含义是该科依照该排名的分数分配合法的方案数。这个值实际上可以通过枚举B神的分数而计算出来，如下
d_i = \sum_{j=1}^{U_i} k^{n-R_i}(U_i-k)^{R_i-1}
考虑到U_i的数据范围，暴力求解这个值是不太可行的。我们知道\sum_i i^n可以表达为一个n+1次多项式，因此d_i可以表达为一个关于U_i的n次多项式，我们求出n+1个点值对然后插值得到d_i即可。

代码

// Code by KSkun, 2018/4
#include <cstdio>
#include <cstring>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 105, MO = 1e9 + 7;

LL n, m, k, C[MAXN][MAXN], u[MAXN], r[MAXN], ptv[MAXN], dp[MAXN][MAXN];

inline LL fpow(LL n, LL k) {
    LL res = 1;
    while(k) {
        if(k & 1) res = res * n % MO;
        n = n * n % MO;
        k >>= 1;
    }
    return res;
}

inline void calc() {
    for(int i = 0; i <= n; i++) {
        C[i][0] = 1;
        for(int j = 1; j <= i; j++) {
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MO;
        }
    }
}

inline LL interpolation(LL u, LL r) {
    memset(ptv, 0, sizeof(ptv));
    // 求n+1个点值
    for(int i = 1; i <= n + 1; i++) {
        for(int j = 1; j <= i; j++) {
            ptv[i] = (ptv[i] + fpow(j, n - r) * fpow(i - j, r - 1) % MO) % MO;
        }
    }
    // 插值
    LL res = 0;
    for(int i = 1; i <= n + 1; i++) {
        LL a = ptv[i], b = 1;
        for(int j = 1; j <= n + 1; j++) {
            if(i == j) continue;
            a = (a * (u - j) % MO + MO) % MO;
            b = (b * (i - j) % MO + MO) % MO;
        }
        res = (res + a * fpow(b, MO - 2) % MO) % MO;
    }
    return res;
}

int main() {
    n = readint(); m = readint(); k = readint();
    for(int i = 1; i <= m; i++) u[i] = readint();
    for(int i = 1; i <= m; i++) r[i] = readint();
    calc();
    dp[0][n - 1] = 1;
    for(int i = 1; i <= m; i++) {
        LL d = interpolation(u[i], r[i]);
        for(int j = k; j <= n - 1; j++) {
            for(int p = j; p <= n - 1 && p - j <= r[i] - 1; p++) {
                dp[i][j] = (dp[i][j] + dp[i - 1][p] * C[p][p - j] % MO 
                    * C[n - 1 - p][r[i] - 1 - (p - j)] % MO * d % MO) % MO;
            }
        }
    }
    printf("%lld", dp[m][k]);
    return 0;
}