十二省联考 2019 皮配 题解

First Post:

Last Update:

做得比较舒服的一道题，还是有启发意义的。

为了与状态变量中的 区分，题面中的 在下文采用大写。

首先考虑 时怎么做，那么对于每个学校而言，派系和阵营的选择是相互独立的。设 ，我们只需保证蓝阵营中的人数在 中，保证鸭派系中的人数在 中即可。

那么设 表示让每个学校选择派系，使得鸭派系中人数为 的方案， 表示让每个城市选择阵营，使得蓝阵营中人数为 的方案。 均可用 的时间背包出来。那么答案就是 。

接下来考虑 时怎么做。我们把不喜欢某个导师的学校叫做特殊点，把有特殊点的城市叫特殊城市。那么我们先把非特殊点加入 中，非特殊城市加入 中。然后考虑特殊城市怎么选阵营，以及特殊点怎么选派系与阵营。

将特殊点拉出来放入一个序列 中，将所属城市相同的特殊点排在一起，然后设 表示 DP 到序列中前 个点，特殊城市中选择蓝阵营的大小和为 ，特殊点中选择鸭派系的大小和为 ，当前城市属于哪个阵营。 可以从 转移过来，要根据 与 所属城市相同或不同分情况转移。因为 不超过 ，且单个状态向后转移的复杂度是 的，这一部分的复杂度就是 。

统计答案时枚举 ，那么其对答案的贡献就是 ，后两个 可以利用 的前缀和 计算。

于是本题就做完了，复杂度为 。

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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5,M = 2.5e3 + 5,M2 = 3e2 + 5,P = 998244353;
inline void Plus(int &x,const int &y) { x += y;if(x >= P) x -= P;}
int n,m,k,lim,Sum;
int C0,C1,D0,D1;
int bel[N],s[N],siz[N];
bool spc[N],spcity[N];
int dislike[N];
int f[M],g[M],sf[M],sg[M];
vector<int> sch[N];
inline void Prework() {
	cin >> n >> m;
	cin >> C0 >> C1 >> D0 >> D1;
	lim = max({C0,C1,D0,D1});
	for(int i = 1;i <= n;i++) siz[i] = spc[i] = spcity[i] = dislike[i] = 0,sch[i].clear();
	for(int i = 0;i <= lim;i++) f[i] = g[i] = 0;
	Sum = 0;
	for(int i = 1;i <= n;i++) cin >> bel[i] >> s[i],siz[bel[i]] += s[i],Sum += s[i];
	cin >> k;
	for(int i = 1,x,y;i <= k;i++)
		cin >> x >> y,spc[x] = spcity[bel[x]] = true,dislike[x] = y;
	for(int i = 1;i <= n;i++) if(spc[i]) sch[bel[i]].push_back(i);
	f[0] = 1;
	for(int i = 1;i <= n;i++) if(!spc[i])
		for(int j = lim;j >= s[i];j--) Plus(f[j],f[j - s[i]]);
	g[0] = 1;
	for(int i = 1;i <= m;i++) if(siz[i] && !spcity[i])
		for(int j = lim;j >= siz[i];j--) Plus(g[j],g[j - siz[i]]);
	sf[0] = f[0];sg[0] = g[0];
	for(int i = 1;i <= lim;i++) sf[i] = (sf[i - 1] + f[i]) % P,sg[i] = (sg[i - 1] + g[i]) % P;
}
inline void Solve0() {
	int l = max(0,Sum - D1),r = D0;
	int ans = 1;
	if(l > r) ans = 0; else ans = 1ll * ans * (sf[r] - (l > 0 ? sf[l - 1] : 0) + P) % P;
	l = max(0,Sum - C1),r = C0;
	if(l > r) ans = 0; else ans = 1ll * ans * (sg[r] - (l > 0 ? sg[l - 1] : 0) + P) % P;
	cout << ans << endl;
}
int dp[2][M][M2][2];
inline void Solve1() {
	int lim2 = 0;
	for(int i = 1;i <= n;i++) if(spc[i]) lim2 += s[i];
	for(int i = 0;i <= lim;i++) for(int j = 0;j < M2;j++) dp[0][i][j][0] = dp[0][i][j][1] = dp[1][i][j][0] = dp[1][i][j][1] = 0;
	dp[0][0][0][0] = 1;
	int op = 0;
	auto DpNext = [&]() {
		for(int j = 0;j <= lim;j++) for(int k = 0;k < M2;k++) dp[op][j][k][0] = dp[op][j][k][1] = 0;
		op ^= 1;
	};
	for(int i = 1;i <= m;i++) {
		if(!sch[i].size()) continue;
		for(int j = 0;j <= lim;j++)
			for(int k = 0;k <= lim2;k++) {
				int now = sch[i][0];
				int id = dislike[sch[i][0]],val = (dp[op][j][k][0] + dp[op][j][k][1]) % P;
				if(!val) continue;
				if(id != 0 && j + siz[i] <= lim && k + s[now] <= lim2) 
					Plus(dp[op ^ 1][j + siz[i]][k + s[now]][0],val);
				if(id != 1 && j + siz[i] <= lim) 
					Plus(dp[op ^ 1][j + siz[i]][k][0],val);
				if(id != 2 && k + s[now] <= lim2) 
					Plus(dp[op ^ 1][j][k + s[now]][1],val);
				if(id != 3) Plus(dp[op ^ 1][j][k][1],val);
			}
		DpNext();
		for(int t = 1;t < sch[i].size();t++) {
			int now = sch[i][t];
			for(int j = 0;j <= lim;j++)
				for(int k = 0;k <= lim2;k++) {
					int id = dislike[now];
					if(id != 0 && k + s[now] <= lim2) Plus(dp[op ^ 1][j][k + s[now]][0],dp[op][j][k][0]);
					if(id != 1) Plus(dp[op ^ 1][j][k][0],dp[op][j][k][0]);
					if(id != 2 && k + s[now] <= lim2) Plus(dp[op ^ 1][j][k + s[now]][1],dp[op][j][k][1]);
					if(id != 3) Plus(dp[op ^ 1][j][k][1],dp[op][j][k][1]);
				}
			DpNext();
		}
	}
	int ans = 0;
	for(int j = 0;j <= lim;j++) for(int k = 0;k <= lim2;k++) {
		int coef = (dp[op][j][k][0] + dp[op][j][k][1]) % P;
		int l = max(0,Sum - D1 - k),r = D0 - k;
		if(l > r) coef = 0; else coef = 1ll * coef * (sf[r] - (l > 0 ? sf[l - 1] : 0) + P) % P;
		l = max(0,Sum - C1 - j);r = C0 - j;
		if(l > r) coef = 0; else coef = 1ll * coef * (sg[r] - (l > 0 ? sg[l - 1] : 0) + P) % P;
		Plus(ans,coef);
	}
	cout << ans << endl;
}
int main() {
	int T;
	cin >> T;
	while(T--) {
		Prework();
		// Solve0();
		Solve1();
	}
	return 0;
}
≡