题面太长，不放了

LOJ3051

Solution

按城市类型把学校排序（把处于相同城市的学校放在一起）之后就可以DP了。首先有两个部分分做法：

  • 算法一：O(nm2)O(nm^2)的暴力DP：

    dp[i][c0][d0][0/1]dp[i][c0][d0][0/1] 表示到第ii个学校，在蓝阵营的有c0c0人，鸭派系的有d0d0人，且第ii个学校在蓝/红阵营的方案数

    暴力枚举每个学校所处阵营和派系转移即可

  • 算法二：k=0k=0 的做法：

    注意到，只要分别确定了每个学校的所属派系，并且确定了每个城市的所属阵营，就能确定每个学校的导师了。并且这两部分是独立的，可以分别求出方案再相乘

    即设f[i][j]f[i][j]表示到第ii个学校，处于鸭派系的有jj人, g[i][j]g[i][j]表示到第ii个城市，处于蓝阵营的有jj人。直接背包转移即可

    这部分复杂度O(nm)O(nm)

k<=30k <= 30，限制比较少，考虑把这两个做法结合起来。定义坏学校为有限制的学校，坏城市为含有坏学校 的城市；好学校/好城市反之

比较暴力的想法是，对所有坏城市中的学校做算法一，对剩下来的学校和好城市做算法二，最后再合并(因为记录的状态是相同，所以可以直接合并)

但是这样复杂度会很高，因为坏城市中可能还有好学校，它们被迫要在复杂度的劣的算法一中被计算（因为要和这个城市中的坏学校保持阵营一致）

优化很简单，考虑在算法一的转移中把阵营和派系的转移拆开，先把坏城市中所有城市的阵营选好，再去选其中所有坏学校的派系，而其中的好学校的派系就可以放到算法二中去选择了。这样做就把这一部分好学校独立开了(因为其阵营已经被选好了)

注意到最终拿到算法一中d0这一维不会超过ks，所以算法一部分的复杂度为O(k2sm)O(k^2sm)

总复杂度为 O(k2sm+nm)O(k^2sm + nm)，代码有点小长

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
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
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
#pragma GCC optimize(3)
#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 MOD = 998244353;

namespace MATH
{
	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;
	}
}

using namespace MATH;

const int MAXN = 1000;
const int MAXS = 600;
const int MAXM = 2500;

int N, K;
int C0, C1, D0, D1;

int belong[MAXN + 5], size[MAXN + 5], ban[MAXN + 5], has_ban[MAXN + 5];
vector <int> City[MAXN + 5];

int A[MAXN + 5], B[MAXN + 5];
int SA[MAXN + 5], SB[MAXN + 5];
int f[MAXN + 5][MAXM + 5], g[MAXN + 5][MAXM + 5]; // f[i][j]: 到第 i 个学校, D0派系有 j 个人的方案数;  g[i][j]: 到第 i 个城市, C0阵营有 j 个人的方案数
int prefix[2][MAXM + 5];

inline void init_prefix ()
{
	prefix[0][0] = f[N][0], prefix[1][0] = g[N][0];
	for (int i = 1; i <= D0; ++i) prefix[0][i] = (prefix[0][i - 1] + f[N][i]) % MOD;
	for (int i = 1; i <= C0; ++i) prefix[1][i] = (prefix[1][i - 1] + g[N][i]) % MOD;
}

inline int get_sum (int l, int r, int k)
{
	if (l > r) return 0;
	if (l == 0) return prefix[k][r];
	return (prefix[k][r] - prefix[k][l - 1] + MOD) % MOD;
}

inline void init_dp ()
{
	for (int i = 1; i <= N; ++i) SA[i] = SA[i - 1] + A[i];
	for (int i = 1; i <= N; ++i) SB[i] = SB[i - 1] + B[i];

	f[0][0] = 1;
	for (int i = 1; i <= N; ++i)
	{
		for (int j = 0; j <= D0; ++j)
		{
			f[i][j] = f[i - 1][j];
			if (j >= A[i] && A[i] && ban[i] == -1) ADD (f[i][j], f[i - 1][j - A[i]]);
		}
	}

	g[0][0] = 1;
	for (int i = 1; i <= N; ++i)
	{
		for (int j = 0; j <= C0; ++j)
		{
			g[i][j] = g[i - 1][j];
			if (j >= B[i] && B[i] && has_ban[i] == 0) ADD (g[i][j], g[i - 1][j - B[i]]);
		}
	}

	init_prefix ();
}

int S[MAXN + 5];

int Dp[2][2][MAXM + 1][MAXS + 1];
pii key[MAXN + 5];
int key_cnt;

inline void Solve ()
{
	init_dp ();

	int lim = 0;
	for (int i = 1; i <= N; ++i) if (has_ban[i])
	{
		key[++key_cnt] = mp (-1, B[i]);
		for (int j = 0; j < City[i].size(); ++j)
		{
			int x = City[i][j];
			if (ban[x] == -1) continue;
			key[++key_cnt] = mp (ban[x], size[x]);
			lim += size[x];
		}
	}

	int n = key_cnt, LIM = min (lim, D0);
	Dp[0][0][0][0] = 1;
	for (int i = 1; i <= n; ++i)
		for (int c0 = 0; c0 <= C0; ++c0)
			for (int d0 = 0; d0 <= LIM; ++d0)
			{
#define now (i & 1)
#define pre (!(i & 1))
				Dp[0][now][c0][d0] = Dp[1][now][c0][d0] = 0;
				if (key[i].x == -1)
				{
					if (c0 >= key[i].y) Dp[0][now][c0][d0] = Dp[0][pre][c0 - key[i].y][d0] + Dp[1][pre][c0 - key[i].y][d0];
					Dp[1][now][c0][d0] = Dp[0][pre][c0][d0] + Dp[1][pre][c0][d0];
				}
				else
				{
					if (key[i].x != 0 && d0 >= key[i].y) Dp[0][now][c0][d0] += Dp[0][pre][c0][d0 - key[i].y];
					if (key[i].x != 1) Dp[0][now][c0][d0] += Dp[0][pre][c0][d0];
					if (key[i].x != 2 && d0 >= key[i].y) Dp[1][now][c0][d0] += Dp[1][pre][c0][d0 - key[i].y];
					if (key[i].x != 3) Dp[1][now][c0][d0] += Dp[1][pre][c0][d0];
				}

				if (Dp[0][now][c0][d0] >= MOD) Dp[0][now][c0][d0] -= MOD;
				if (Dp[1][now][c0][d0] >= MOD) Dp[1][now][c0][d0] -= MOD;

//				DEBUG (i);
//				cout << Dp[0][now][c0][d0] << ' ' << Dp[1][now][c0][d0] << endl;
#undef now
#undef pre
			}

	int ans = 0;
	for (int c0 = 0; c0 <= C0; ++c0)
		for (int d0 = 0; d0 <= LIM; ++d0)
		{
			int sum = (Dp[0][n & 1][c0][d0] + Dp[1][n & 1][c0][d0]) % MOD;
			int sum_d = get_sum (max (0, SA[N] - D1 - d0), D0 - d0, 0);
			int sum_c = get_sum (max (0, SA[N] - C1 - c0), C0 - c0, 1);

			ADD (ans, (LL) sum * sum_c % MOD * sum_d % MOD);
		}

	cout << ans << endl;
}

inline void Input ()
{
	N = read<int>(), read<int>();
	C0 = read<int>(), C1 = read<int>(), D0 = read<int>(), D1 = read<int>();

	for (int i = 1; i <= N; ++i)
	{
		belong[i] = read<int>(), size[i] = read<int>();
		A[i] = size[i], B[belong[i]] += size[i];
		City[belong[i]].pb(i);
	}

	K = read<int>();
	while (K--) 
	{
		int x = read<int>(), p = read<int>();
		ban[x] = p;
		has_ban[belong[x]] = 1;
	}
}

inline void Clear ()
{
	for (int i = 0; i < 2; ++i) for (int j = 0; j < 2; ++j)
		for (int c0 = 0; c0 <= C0; ++c0)
			for (int d0 = 0; d0 <= MAXS; ++d0)
				Dp[j][i][c0][d0] = 0;
	for (int i = 1; i <= N; ++i)
	{
		City[i].clear(); 
		B[i] = has_ban[i] = 0, ban[i] = -1;
	}

	key_cnt = 0;
}

inline void Init ()
{
	memset (ban, -1, sizeof ban);
}

int main ()
{

	freopen("mentor.in", "r", stdin);
	freopen("mentor.out", "w", stdout);

	int Te = read<int>();

	Init ();
	while (Te--)
	{
		Input ();
		Solve ();
		Clear ();
	}

	return 0;
}