「SHOI2016」成绩比较

发表于
https://loj.ac/problem/2026

题目链接

「SHOI2016」成绩比较

做法

设 $ val_i $ 表示第 $ i $ 门课分数分配的方案数。
$ f_{i, j} $ 表示前 i 门课 B神 吊打 j 人的方案数。

$$
f_{i, j} = \sum_{i = j}^{n} f_{i - 1, k} \binom{k}{j}\binom{n - k - 1}{rank_i - 1 - (k - j)}val_i
$$

即从原来吊打 k 个人减为 j 个人（k 里选 j 个），再从剩下的人中选一些排在他前面。

$$
val_i = \sum_{j = 1}^{mx_i} j^{n - rank_i}(mx_i - j)^{rank_i - 1}
$$

感性理解发现这个式子可以被描述成关于 $ mx_i $ 的 n 次多项式。
拉格朗日插值即可。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
using namespace std;
const int mod = 1e9 + 7;
const int N = 210;
int n, m, k, mx[N], rnk[N], pw[N][N];
int f[N][N], c[N][N];
int val[N];

inline int C(int x, int y) { return (x < 0 || y < 0 || x < y) ? 0 : c[x][y]; }
int ksm(int x, int y = mod - 2) {
	int w = 1; for(; y; y >>= 1, x = 1ll * x * x % mod) if(y & 1) w = 1ll * x * w % mod; return w;
}
int solve(int x) {
	int res = 0;
	if(mx[x] <= 100) {
		rep(i, 1, mx[x]) res = (res + 1ll * pw[i][n - rnk[x]] * pw[mx[x] - i][rnk[x] - 1]) % mod;
		return res;
	}
	rep(i, 1, n + 1) {
		val[i] = 0;
		rep(j, 1, i) val[i] = (val[i] + 1ll * pw[j][n - rnk[x]] * pw[i - j][rnk[x] - 1]) % mod;
	}
	rep(i, 1, n + 1) {
		int mu1 = 1, mu2 = 1;
		rep(j, 1, n + 1) if(j != i) {
			mu1 = 1ll * mu1 * (mod + mx[x] - j) % mod;
			mu2 = 1ll * mu2 * (mod + i - j) % mod;
		}
		res = (res + 1ll * mu1 * ksm(mu2) % mod * val[i]) % mod;
	}
	return res;
}
int main() {
	c[0][0] = 1;
	rep(i, 1, 200) { c[i][0] = 1; rep(j, 1, i) c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod; }
	rep(i, 0, 200) { pw[i][0] = 1; rep(j, 1, 200) pw[i][j] = 1ll * pw[i][j - 1] * i % mod; }
	scanf("%d%d%d", &n, &m, &k);
	rep(i, 1, m) scanf("%d", &mx[i]);
	rep(i, 1, m) scanf("%d", &rnk[i]);
	f[0][n - 1] = 1;
	rep(i, 1, m) {
		int mu = solve(i);
		rep(j, k, n - 1) rep(k, j, n - 1) {
			int w = 1ll * C(k, j) * C(n - k - 1, rnk[i] - 1 - (k - j)) % mod * f[i - 1][k] % mod;
			f[i][j] = (f[i][j] + 1ll * mu * w) % mod;
		}
	}
	printf("%d\n", f[m][k]);
	return 0;
}