洛谷P3270 [JLOI2016] 成绩比较题解

题目链接：P3270 [JLOI2016] 成绩比较

题意：

G 系共有 \(N\) 位同学，\(M\) 门必修课。这 \(N\) 位同学的编号为 \(0\) 到 \(N-1\) 的整数，其中 B 神的编号为 \(0\) 号。这 \(M\) 门必修课编号为 \(0\) 到 \(M-1\) 的整数。一位同学在必修课上可以获得的分数是 \(1\) 到 \(U_i\) 中的一个整数。

如果在每门课上 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\) 个正整数，依次表示每门课的最高分 \(U_i\)。

第三行包含 \(M\) 个正整数，依次表示 B 神在每门课上的排名 \(R_i\)。

数据保证至少有 \(1\) 种情况使得 B 神说的话成立。

输出格式：

仅一行一个正整数，表示满足条件的情况数模 \(10^9+7\) 的余数。

数据范围：

\(1\leq N\leq 100\)，\(1\leq M\leq 100\)，\(1\leq U_i\leq 10^9\)，\(1\leq R_i\leq N\)。

设 \(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\) 位。

最后每个人有一个分数，需要乘上 \(T_i = \sum_{j=1}^{u_i} j^{n-r_i}\left(u_i-j\right)^{r_i-1}\) ，那么完整的方程为 \[ f(i,j)=T_i\sum_{k=0}^{\min \left(n-j-1, r_i-1\right)} \binom{j+k}{k}\binom{n-1-j-k}{r_i-1-k}f(i-1, j+k) \] 其中 \(T_i\) 是复杂度瓶颈。注意到这个东西和 CF622F 的思路类似，考虑拉格朗日插值法即可。

时间复杂度 \(\mathcal{O}(n^2m)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 1e9 + 7;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
void add(int &x, int y) { (x += y) >= mod ? x -= mod : 0; }
int mo(int x) { return x < 0 ? x + mod : x; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(114))

int n, m, K, u[N], r[N], y[N * 2], t[N], C[N][N], f[N][N];
int qpow(int a, int b)
{
    int res = 1;
    for(a %= mod; b; b >>= 1, a = a * a % mod)
        if(b & 1) res = res * a % mod;
    return res;
}
int solve(int k)
{
    int res = 0;
    rep(i, 1, n * 2)
    {
        int prod = y[i];
        rep(j, 1, n * 2) if(j != i)
        {
            const int _1 = prod * mo(k - j) % mod;
            const int _2 = qpow(mo(i - j), mod - 2) % mod;
            prod = _1 * _2 % mod;
        }
        add(res, prod); 
    }
    return res;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m >> K;
    rep(i, 1, m) { cin >> u[i]; } rep(i, 1, m) { cin >> r[i]; }
    rep(i, 0, n) C[i][0] = 1;
    rep(i, 1, n) rep(j, 1, i) add(C[i][j] = C[i - 1][j - 1], C[i - 1][j]);
    f[0][n - 1] = 1;
    rep(i, 1, m)
    {
        rep(j, 1, n * 2) { add(y[j] = y[j - 1], qpow(j, n - r[i]) * qpow(u[i] - j, r[i] - 1) % mod); }
        t[i] = solve(u[i]);
        rep(j, 0, n - 1) rep(k, 0, min(n - j - 1, r[i] - 1))
        {
            const int _1 = f[i - 1][j + k] * C[j + k][k] % mod;
            const int _2 = C[n - 1 - j - k][r[i] - 1 - k] * t[i] % mod;
            add(f[i][j], _1 * _2 % mod);
        }
    }
    cout << f[m][K] << '\n';
    return 0;
}