自动搬运

查看原文

来自洛谷，原作者为

	Mirach 诶这里还可以填东西？

搬运于2025-08-24 22:09:06，当前版本为作者最后更新于2019-05-07 21:37:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

安利博客：博主一般不会在这个博客里灌水，题目都还是挺有质量的qwq

Problem

题意概要：有 $c$ 个豆荚，共 $n$ 颗豆子，每颗豆子都有自己的重量，现在需要将给豆子设定为 (黄色/绿色,圆粒/皱粒)，要求满足以下条件：

• 给定这四种性状的阀值 $C_0,C_1,D_0,D_1$，要求为这种性状的豆子重量和不能超过该阀值
• 与此同时，这 $n$ 颗豆子中存在 $k$ 颗顽皮豆，顽皮豆都有自己的想法，比如拒绝成为 (黄圆/黄皱/绿圆/绿皱)
• 同一个豆荚里的豆子必须 同时为黄色 或 同时为绿色

求有多少种给豆子设定的方案，对 $998244353$ 取模

$n,c\leq 10^3,k\leq 30$

设 $M=\max\{C_0,C_1,D_0,D_1\}$，$M\leq 2500$

豆子重量不超过 $\min\{M,10\}$

Solution

首先有一个 $O(nM^3)$ 的暴力：设定三维——“黄圆”、“黄皱”和“绿圆”的豆子重量和，枚举每一颗豆子去更新。酱紫就有 $30pts+$

其次有一个 $O(nM^2)$ 的暴力：设定两维——“黄色”和“圆粒”的重量和。酱紫有 $50pts$

再者考虑 $k=0$：所有豆子都没有限制，考虑将豆子进行划分。发现无论是先划分 黄/绿 还是先划分 圆/皱 都对结果没有影响，对应的这两者可以分开计算最后相乘：

设 $f[i]$ 表示黄色重量和为 $i$ 的方案数，$g[i]$ 表示圆粒重量和为 $i$ 的方案数，这两个数组可以 $O(nM)$ 背包求得，然后答案就为（设所有豆子重量和为 $S$）：

做到这再算上前边的就有 $70pts$

现在考虑将顽皮豆加入 肯德基豪华午餐 考虑范畴

称这些顽皮豆为“有毒”的豆子，对应的豆荚一定为“有毒”的豆荚

（在阅读下面内容时，请时刻牢记：对于 黄/绿 的划分是以“豆荚”为单位的；对于 圆/皱 的划分是以“豆子”为单位的）

• 对于“无毒”的豆荚，仍然可以正常考虑其 黄/绿 的相对性状，dp 数组设为 $f$
• 对于“无毒”的豆子，仍然可以正常考虑其 圆/皱 的相对性状，dp 数组设为 $g$（因为“有毒”的豆子可能会影响整个豆荚的 黄/绿 性状，所以这里不考虑颜色性状）

那么依照前一档部分分，这两个是可以乘起来的

不难发现，求完 $f$ 后就不用再管“无毒”豆荚的 黄/绿，求完 $g$ 后就不用再管“无毒”豆子的 圆/皱，余下需要考虑的就只有“有毒”豆子的 黄/绿、圆/皱 了

由于“有毒”的豆子不多，只有 $30$ 个，可以对这一部分考虑采用 $50pts$ 那一档的暴力 Dp，dp 数组设为 $F$（注意 黄/绿 维度用的是整个豆荚的重量，圆/皱 维度用的是单个豆子的重量）

最后只要枚举“有毒”豆子的两个性状的重量 $F$，会得到一个 黄/绿 划分和一个 圆/皱 划分，考虑用 $f$ 去匹配 黄/绿（这样所有“有毒”与“无毒”豆荚的 黄/绿 就处理完了），用 $g$ 去匹配 圆/皱 划分（这样所有“有毒”与“无毒”的豆子的 圆/皱 就处理完了），乘起来即可

计算时间复杂度（空间反正是 $O(M^2)$ 的）：

• 计算 $f$ 的 dp 是 $O(cM)$ 的
• 计算 $g$ 的 dp 是 $O(nM)$ 的
• 计算 $F$ 的 dp 是 $O(kM^2)$ 的，但是由于豆子的重量 $s\leq 10$，所以其实是 $O(k^2sM)$ 的
• 统计答案是 $O(ksM)$ 的

总时间复杂度为 $O((c+n)M+k^2sM)$

另说，这题只考察了联赛级别的知识点——背包，包括：分部背包、双线程背包、背包合并……

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline void read(int&x){
	char ch=getchar();x=0;while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
}

const int p = 998244353;
inline int qm(const int x) {return x < p ? x : x - p;}
inline void pls(int&x, const int&y) {x = x+y < p ? x+y : x+y-p;}

const int N = 1010, M = 2503;
bool city_hate[N];
int city_sum[N], hate[N], b[N], s[N];
int f[M], pre_f[M], F[M][M];
int g[M], pre_g[M], G[M][M];
int n, c;

void work() {
	read(n), read(c);
	int C0, C1, D0, D1, ALL = 0;
	for(int i=1;i<=c;++i) city_hate[i] = false, city_sum[i] = 0;
	read(C0), read(C1), read(D0), read(D1);
	for(int i=1;i<=n;++i) read(b[i]), read(s[i]), city_sum[b[i]] += s[i], hate[i] = -1, ALL += s[i];
	int K, x; read(K);
	while(K--) read(x), read(hate[x]), city_hate[b[x]] = true;
	
	memset(f, 0, sizeof f), pre_f[0] = f[0] = 1;
	for(int i=1;i<=c;++i)
		if(!city_hate[i] and city_sum[i])
			for(int j = C0, ts = city_sum[i]; j >= ts; -- j)
				pls(f[j], f[j-ts]);
	for(int i=1;i<=C0;++i) pre_f[i] = qm(pre_f[i-1] + f[i]);
	
	memset(g, 0, sizeof g), pre_g[0] = g[0] = 1;
	for(int i=1;i<=n;++i)
		if(-1 == hate[i])
			for(int j = D0, ts = s[i]; j >= ts; -- j)
				pls(g[j], g[j-ts]);
	for(int i=1;i<=D0;++i) pre_g[i] = qm(pre_g[i-1] + g[i]);
	
	int Cs = 0, Ss = 0;
	memset(F, 0, sizeof F), F[0][0] = 1;
	memset(G, 0, sizeof G);
	for(int ct = 1; ct <= c; ++ ct)
		if(city_hate[ct]) {
			Cs += city_sum[ct], Cs = min(Cs, C0);
			for(int i=0;i<=Cs;++i)
			for(int j=0;j<=Ss;++j) G[i][j] = F[i][j];
			
			for(int a=1;a<=n;++a)
				if(b[a] == ct and ~hate[a]) {
					const int t = s[a];
					Ss += t, Ss = min(Ss, D0);
					if(hate[a] == 1)
						for(int i=0;i<=Cs;++i) {
							for(int j=Ss;j>=t;--j) F[i][j] = F[i][j-t];
							for(int j=t-1;~j;--j) F[i][j] = 0;
						}
					if(hate[a] >= 2)
						for(int i=0;i<=Cs;++i)
						for(int j=Ss;j>=t;--j) pls(F[i][j], F[i][j-t]);
					if(hate[a] == 3)
						for(int i=0;i<=Cs;++i) {
							for(int j=Ss;j>=t;--j) G[i][j] = G[i][j-t];
							for(int j=t-1;~j;--j) G[i][j] = 0;
						}
					if(hate[a] <= 1)
						for(int i=0;i<=Cs;++i)
						for(int j=Ss;j>=t;--j) pls(G[i][j], G[i][j-t]);
				}
			for(int j=0,t=city_sum[ct];j<=Ss;++j) {
				for(int i=Cs;i>=t;--i) F[i][j] = F[i-t][j];
				for(int i=t-1;~i;--i) F[i][j] = 0;
			}
			for(int i=0;i<=Cs;++i)
			for(int j=0;j<=Ss;++j)
				pls(F[i][j], G[i][j]);
		}
	
	int res = 0;
	for(int i=0;i<=Cs;++i)
	for(int j=0;j<=Ss;++j) {
		int l1 = max(0, ALL - C1 - i), r1 = C0 - i; if(l1 > r1) continue;
		int l2 = max(0, ALL - D1 - j), r2 = D0 - j; if(l2 > r2) continue;
		int vf = pre_f[r1]; if(l1) vf += p - pre_f[l1-1];
		int vg = pre_g[r2]; if(l2) vg += p - pre_g[l2-1];
		pls(res, (ll)vf * vg%p * F[i][j]%p);
	}
	printf("%d\n", res);
}

int main() {
	int T; read(T);
	while(T--) work();
	return 0;
}