LOJ 2026

Solution

先从 n1n - 1个人里安排kk个人被碾压,然后再分配具体分数,乘起来即为答案

先考虑第一部分。容斥,设f(i)f(i)表示钦定ii个人被碾压,其他人任意的方案数。依次考虑每个科目,对于第jj个科目,比BB成绩高的一定是剩余的n1in - 1 - i个人中的某ri1r_i - 1个,所以有

f(i)=j=1m(n1irj1)ans=i=kn1(1)ik(n1k)(ik)f(i) \begin{aligned} f(i) &= \prod_{j=1}^m \binom{n - 1 - i}{r_j - 1} \\ ans &= \sum_{i=k}^{n-1} (-1)^{i-k} \binom{n-1}{k} \binom{i}{k} f(i) \end{aligned}

对于第二问,对每个科目分开计算,然后乘在一起。对于第ii个科目,暴力做法是枚举BB的分数,答案为j=1uijnri(uij)ri1\sum_{j = 1}^{u_i} j^{n - r_i} (u_i - j)^{r_i - 1}

因为uiu_i很大而nn很小,考虑枚举总共出现了几种不同的分数,然后是一个很经典的容斥方法: 设g(j)g(j)表示用不超过jj种分数分配的方案数,h(j)h(j)表示用恰好jj种分数分配的方案数

那么h(j)=g(j)t=1j1(jk)h(k)h(j) = g(j) - \sum_{t = 1}^{j - 1} \binom{j}{k} h(k),对答案的贡献即为j=1n(uij)h(j)\sum_{j=1}^{n} \binom{u_i}{j} h(j)

复杂度O(m2n)O(m^2n)

Code

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
#include <iostream>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <climits>
#include <queue>
#include <set>
#include <cmath>
#include <map>
#include <bitset>
#include <fstream>
#include <tr1/unordered_map>
#include <assert.h>

#define x first
#define y second
#define y0 Y0
#define y1 Y1
#define mp make_pair
#define pb push_back
#define DEBUG(x) cout << #x << " = " << x << endl;

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
T sum = 0, fl = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch - '0');
return sum * fl;
}

inline void proc_status ()
{
ifstream t ("/proc/self/status");
cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int MAXN = 100;
const int MOD = 1e9 + 7;

int N, M, K;
int U[MAXN + 5], R[MAXN + 5];

namespace MATH
{
int fac[MAXN + 5], ifac[MAXN + 5], inv[MAXN + 5];

inline void ADD (int &a, int b) { if ((a += b) >= MOD) a -= MOD; }

inline int Pow (int a, int b)
{
int ans = 1;
for (int i = b; i; i >>= 1, a = (LL) a * a % MOD) if (i & 1) ans = (LL) ans * a % MOD;
return ans;
}

inline void init (int n = MAXN + 1)
{
fac[0] = 1; for (int i = 1; i <= n; ++i) fac[i] = (LL) fac[i - 1] * i % MOD;
ifac[n] = Pow (fac[n], MOD - 2); for (int i = n - 1; i >= 0; --i) ifac[i] = (LL) ifac[i + 1] * (i + 1) % MOD;
for (int i = 0; i < n; ++i) inv[i + 1] = (LL) fac[i] * ifac[i + 1] % MOD;
}

inline int C (int n, int m) { if (n < m || n < 0 || m < 0) return 0; return (LL) fac[n] * ifac[m] % MOD * ifac[n - m] % MOD; }
}

using namespace MATH;

inline int calc1 ()
{
int ans = 0;
for (int i = K; i < N; ++i)
{
int sum = (LL) C (N - 1, i) * C (i, K) % MOD;
for (int j = 1; j <= M; ++j)
sum = (LL) sum * C (N - 1 - i, R[j] - 1) % MOD;
if ((i - K) & 1) ADD (ans, MOD - sum);
else ADD (ans, sum);
}
return ans;
}

inline int calc2 ()
{
static int H[MAXN + 5][MAXN + 5], G[MAXN + 5][MAXN + 5];

int ans = 1;
for (int i = 1; i <= M; ++i)
{
int sum = 0, binom = 1;
for (int j = 1; j <= min (U[i] + 1, N); ++j)
{
for (int k = 1; k <= j; ++k)
ADD (G[i][j], (LL) Pow (k, N - R[i]) * Pow (j - k, R[i] - 1) % MOD);
H[i][j] = G[i][j];
for (int k = 1; k < j; ++k)
ADD (H[i][j], MOD - (LL) C (j, k) * H[i][k] % MOD);

binom = (LL) binom * (U[i] - j + 1) % MOD * inv[j] % MOD;

ADD (sum, (LL) binom * H[i][j] % MOD);
}

ans = (LL) ans * sum % MOD;
}

return ans;
}

inline void Solve ()
{
int ans = 1;
ans = (LL) ans * calc1 () % MOD;
ans = (LL) ans * calc2 () % MOD;
cout << ans << endl;
}

inline void Input ()
{
N = read<int>(), M = read<int>(), K = read<int>();
for (int i = 1; i <= M; ++i) U[i] = read<int>();
for (int i = 1; i <= M; ++i) R[i] = read<int>();
}

int main ()
{

#ifdef hk_cnyali
freopen("A.in", "r", stdin);
freopen("A.out", "w", stdout);
#endif

MATH :: init ();
Input ();
Solve ();

return 0;
}