「BZOJ 4559」成绩比较-拉格朗日插值

$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$ 的余数就可以了。

链接

BZOJ 4559

题解

令 $f(i, j)$ 表示前 $i$ 个学科,不被碾压的人数为 $j$ 的方案数。
考虑状态转移,从 $f(i, j)$ 转移到 $f(i, k)$,$\text{ex} = k - j$ 表示新增加的不被碾压的人数,$\text{old} = R_i - i - \text{ex}$ 表示原本就存在的不被碾压的人数,那么要从 $j$ 个人中选出 $\text{old}$ 个人,从 $n - j - 1$ 个人中选出 $\text{ex}$ 个人,方案数为 ${{j}\choose{t_2}}\times{n-j-1\choose{t_1}}$

在每种方案下,当分数为 $x$ 时,$R_i−1$ 个人的分数要超过 $x$,$n−R_i$ 个人的分数不超过 $x$,即方案数为
$$\sum_{x=1}^{U_i} (U_i-x)^{R_i-1}\times x^{n-R_i}$$
所以,转移方程为
$$f(i,k)\leftarrow f(i,j)\times {{j}\choose{t_2}}\times{n-j-1\choose{t_1}}\times(\sum_{x=1}^{U_i} (U_i-x)^{R_i-1}\times x^{n-R_i})$$
由于 $U_i$ 很大,不能直接求,我们可以对 $\sum\limits_{x=1}^{U_i} (U_i-x)^{R_i-1}\times x^{n-R_i}$ 插值求。

时间复杂度 $O(mn \log U + mn ^ 2)$

代码

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
/**
* Copyright (c) 2017, xehoth
* All rights reserved.
* 「BZOJ 4559」成绩比较 18-09-2017
* 拉格朗日插值
* @author xehoth
*/
#include <bits/stdc++.h>
namespace IO {
inline char read() {
static const int IN_LEN = 1000000;
static char buf[IN_LEN], *s, *t;
s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin) : 0;
return s == t ? -1 : *s++;
}
template <typename T>
inline void read(T &x) {
static char c;
static bool iosig;
for (c = read(), iosig = false; !isdigit(c); c = read()) {
if (c == -1) return;
c == '-' ? iosig = true : 0;
}
for (x = 0; isdigit(c); c = read()) x = x * 10 + (c ^ '0');
iosig ? x = -x : 0;
}
inline void read(char &c) {
while (c = read(), isspace(c) && c != -1)
;
}
inline int read(char *buf) {
register int s = 0;
register char c;
while (c = read(), isspace(c) && c != -1)
;
if (c == -1) {
*buf = 0;
return -1;
}
do
buf[s++] = c;
while (c = read(), !isspace(c) && c != -1);
buf[s] = 0;
return s;
}
const int OUT_LEN = 1000000;
char obuf[OUT_LEN], *oh = obuf;
inline void print(char c) {
oh == obuf + OUT_LEN ? (fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf) : 0;
*oh++ = c;
}
template <typename T>
inline void print(T x) {
static int buf[30], cnt;
if (x == 0) {
print('0');
} else {
x < 0 ? (print('-'), x = -x) : 0;
for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 | 48;
while (cnt) print((char)buf[cnt--]);
}
}
inline void print(const char *s) {
for (; *s; s++) print(*s);
}
inline void flush() { fwrite(obuf, 1, oh - obuf, stdout); }
struct InputOutputStream {
template <typename T>
inline InputOutputStream &operator>>(T &x) {
read(x);
return *this;
}
template <typename T>
inline InputOutputStream &operator<<(const T &x) {
print(x);
return *this;
}
~InputOutputStream() { flush(); }
} io;
}
namespace {
using IO::io;
const int MOD = 1000000007;
const int MAXN = 110;
#define long long long
inline int modPow(int a, int b) {
register int ret = 1;
for (; b; b >>= 1, a = (long)a * a % MOD)
(b & 1) ? ret = (long)ret * a % MOD : 0;
return ret;
}
struct Task {
int inv[MAXN + 1], n, m, k;
int c[MAXN + 1][MAXN + 1];
int u[MAXN + 1], r[MAXN + 1];
int f[MAXN + 1][MAXN + 1];
int s[MAXN + 1];
inline void init(const int n) {
inv[0] = inv[1] = 1;
for (register int i = 2; i <= n; i++)
inv[i] = (long)i * inv[i - 1] % MOD;
inv[n] = modPow(inv[n], MOD - 2);
for (register int i = n - 1; i >= 0; i--)
inv[i] = inv[i + 1] * (i + 1ll) % MOD;
for (register int i = 0; i <= n; i++) {
c[i][0] = 1;
for (register int j = 1; j <= i; j++)
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MOD;
}
}
inline int interpolation(int u, int r, int n) {
static int f[MAXN + 3], pre[MAXN + 3], suf[MAXN + 3];
f[0] = 0;
for (register int i = 1; i <= n + 1; i++) {
f[i] = (f[i - 1] + (long)modPow(i, n - r) * modPow(u - i, r - 1)) %
MOD;
if (u == i) return f[i];
}
pre[0] = suf[n + 2] = 1;
for (register int i = 1; i <= n + 1; i++)
pre[i] = (long)pre[i - 1] * (u - i) % MOD;
for (register int i = n + 1; i; i--)
suf[i] = (long)suf[i + 1] * (u - i) % MOD;
register int ret = 0;
for (register int i = 1, tmp; i <= n + 1; i++) {
tmp = (long)f[i] * pre[i - 1] % MOD * suf[i + 1] % MOD *
inv[i - 1] % MOD * inv[n + 1 - i] % MOD;
if ((n + 1 - i) % 2) tmp = MOD - tmp;
ret = (ret + tmp) % MOD;
}
return ret;
}
inline void solve() {
std::string a;
a.era
io >> n >> m >> k;
for (register int i = 1; i <= m; i++) io >> u[i];
for (register int i = 1; i <= m; i++) io >> r[i];
init(n);
for (register int i = 1; i <= m; ++i)
s[i] = interpolation(u[i], r[i], n);
f[0][0] = 1;
for (register int i = 0; i < m; i++) {
for (register int j = 0; j <= n; j++) {
if (f[i][j] != 0) {
for (register int k = j, ex, old; k <= n; k++) {
ex = k - j, old = r[i + 1] - 1 - ex;
if (old < 0) break;
f[i + 1][k] =
(f[i + 1][k] +
(long)c[j][old] * c[n - j - 1][ex] % MOD *
s[i + 1] % MOD * f[i][j] % MOD) %
MOD;
}
}
}
}
io << f[m][n - k - 1];
}
} task;
#undef long
}
int main() {
task.solve();
return 0;
}
分享到