Loj 3051 皮配

Posted on | Edited on | Views:

背包 dp .

如果直接裸上一个背包计数,那么阵营和派系两种限制的状态都要记录.

即,设 $f(i,x,y)$ 表示考虑了前 $i$ 个城市的所有学校,加入蓝阵营的有 $x$ 人,加入鸭派系的有 $y$ 人的方案数.

时间复杂度 $O(nm^2)​$ ,无法通过.

注意到有限制的学校数目 $k$ 比较小,可以将有限制的学校和没有限制的学校分开处理.

设 $f(i,x,y)$ 表示考虑了前 $i$ 个包含某个有限制学校的城市,加入蓝阵营的有 $x$ 人,加入鸭派系的有 $y$ 人的方案数.

而对于没有限制的学校,可以发现学校选择的派系是不影响城市选择的阵营的,可以分开 dp ,最后将方案数相乘.

设 $g(i,x)$ 表示考虑了前 $i$ 个没有限制学校的城市,加入蓝阵营的有 $x$ 人的方案数.

设 $h(i,y)$ 表示考虑了前 $i$ 个没有限制的学校,加入鸭派系的有 $y$ 人的方案数.

最后统计答案时,每个 $f(x,y)$ 对应的合法的 $g,h$ 都是一段区间,处理出前缀和后即可统计贡献.

时间复杂度 $O(10\cdot k^2m+nm)$ .

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
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out = 0, fh = 1;
	char jp = getchar();
	while ((jp > '9' || jp < '0') && jp != '-')
		jp = getchar();
	if (jp == '-')
		fh = -1, jp = getchar();
	while (jp >= '0' && jp <= '9')
		out = out * 10 + jp - '0', jp = getchar();
	return out * fh;
}
const int P = 998244353;
int add(int a, int b)
{
	return a + b >= P ? a + b - P : a + b;
}
void inc(int &a, int b)
{
	a = add(a, b);
}
int mul(int a, int b)
{
	return 1LL * a * b % P;
}
const int N = 2500 + 10;
void cl(int *a, int n)
{
	for (int i = 0; i <= n; ++i)
		a[i] = 0;
}
void cl(int a[N][N], int n, int m)
{
	for (int i = 0; i <= n; ++i)
		for (int j = 0; j <= m; ++j)
			a[i][j] = 0;
}
int n, m, k, tot, pt, C0, C1, D0, D1;
int vis[N], siz[N], bel[N], hate[N];
vector<int> vec[N];
int g[N][N], h[N][N], f[2][N][N], id, cnt, ht, ts[N];
void dp_g()
{
	cl(g[0], C0);
	g[0][0] = 1;
	for (int c = 1, i = 0; c <= m; ++c)
		if (!vis[c] && !vec[c].empty())
		{
			cnt = ++i;
			cl(g[i], C0);
			int s = 0;
			for (int x : vec[c])
				s += siz[x];
			for (int j = 0; j <= C0; ++j) 
				if (g[i - 1][j])
				{
					if (j + s <= C0)
						inc(g[i][j + s], g[i - 1][j]);
					inc(g[i][j], g[i - 1][j]);
				}
		}
	for (int i = 1; i <= C0; ++i)
		inc(g[cnt][i], g[cnt][i - 1]);
}
int th[2][N][N];
void dp_h()
{
	cl(h[0], D0);
	h[0][0] = 1;
	for (int x = 1, i = 0; x <= n; ++x)
		if (hate[x] == -1)
		{
			ht = ++i;
			cl(h[i], D0);
			int s = siz[x];
			for (int j = 0; j <= D0; ++j) 
				if (h[i - 1][j])
				{
					if (j + s <= D0)
						inc(h[i][j + s], h[i - 1][j]);
					inc(h[i][j], h[i - 1][j]);
				}
		}
	for (int i = 1; i <= D0; ++i)
		inc(h[ht][i], h[ht][i - 1]);
}
void dp_f()
{
	id = 0;
	cl(f[id], C0, D0);
	f[id][0][0] = 1;
	for (int c = 1; c <= m; ++c)
		if (vis[c])
		{
			id ^= 1;
			cl(f[id], C0, D0);
			int td = 0;
			for (int i = 0; i <= C0; ++i)
				for (int j = 0; j <= D0 && j <= pt; ++j)
					th[0][i][j] = f[id ^ 1][i][j];
			int tp = pt;
			int s = ts[c];
			
			// Blue
			for (int x : vec[c]) if (hate[x] != -1)
			{
				td ^= 1;
				cl(th[td], C0, D0);
				for (int i = 0; i + s <= C0; ++i)
				for (int j = 0; j <= D0 && j <= pt; ++j) 
				if (th[td ^ 1][i][j])
				{
					if (hate[x] != 0 && j + siz[x] <= D0)
						inc(th[td][i][j + siz[x]], th[td ^ 1][i][j]);
					if (hate[x] != 1)
						inc(th[td][i][j], th[td ^ 1][i][j]);
				}
				pt += siz[x];
			}
			for (int i = 0; i + s <= C0; ++i)
				for (int j = 0; j <= D0 && j <= pt; ++j)
					inc(f[id][i + s][j], th[td][i][j]);
			
			// Red
			pt = tp;
			td = 0;
			for (int i = 0; i <= C0; ++i)
				for (int j = 0; j <= D0 && j <= pt; ++j)
					th[0][i][j] = f[id ^ 1][i][j];
			for (int x : vec[c]) if (hate[x] != -1)
			{
				td ^= 1;
				cl(th[td], C0, D0);
				for (int i = 0; i <= C0; ++i)
				for (int j = 0; j <= D0 && j <= pt; ++j) 
				if (th[td ^ 1][i][j])
				{
					if (hate[x] != 2 && j + siz[x] <= D0)
						inc(th[td][i][j + siz[x]], th[td ^ 1][i][j]);
					if (hate[x] != 3)
						inc(th[td][i][j], th[td ^ 1][i][j]);
				}
				pt += siz[x];
			}
			for (int i = 0; i <= C0; ++i)
				for (int j = 0; j <= D0 && j <= pt; ++j)
					inc(f[id][i][j], th[td][i][j]);
		}
}
void solve()
{
	n = read(), m = read();
	tot = cnt = ht = 0;
	for (int i = 1; i <= m; ++i)
		vec[i].clear(), vis[i] = ts[i] = 0;
	C0 = read(), C1 = read(), D0 = read(), D1 = read();
	for (int i = 1; i <= n; ++i)
	{
		bel[i] = read(), siz[i] = read(), hate[i] = -1;
		tot += siz[i];
		vec[bel[i]].push_back(i);
		ts[bel[i]] += siz[i];
	}
	k = read();
	pt = 0;
	for (int i = 1; i <= k; ++i)
	{
		int x = read();
		hate[x] = read();
		vis[bel[x]] = 1;
	}
	dp_g();
	dp_h();
	dp_f();
	int ans = 0;
	for (int x = 0; x <= C0; ++x) if (pt - x <= C1)
		for (int y = 0; y <= D0 && y <= pt; ++y) 
		if (pt - y <= D1 && f[id][x][y])
		{
			int tmp = f[id][x][y], L, R;
			L = max(0, tot - C1 - x), R = min(tot - pt, C0 - x);
			if (L <= R)
				tmp = mul(tmp, add(g[cnt][R], P - (L ? g[cnt][L - 1] : 0)));
			else
				tmp = 0;
			L = max(0, tot - D1 - y), R = min(tot - pt, D0 - y);
			if (L <= R)
				tmp = mul(tmp, add(h[ht][R], P - (L ? h[ht][L - 1] : 0)));
			else
				tmp = 0;
			inc(ans, tmp);
		}
	printf("%d\n", ans);
}
int main()
{
	int T = read();
	while (T--)
		solve();
	return 0;
}