自动搬运

查看原文

来自洛谷，原作者为

	Register_int 分道扬镳

搬运于2025-08-24 22:55:07，当前版本为作者最后更新于2024-02-02 09:40:29，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

场外选手。

不妨算出每个题 $i$ 在多少种方案中能被提交。题目中“将一道题状态改为结果不可见”显然只是将题目扔到末尾，所以：

• 当 $i$ 结果可见时，他能否提交只跟编号比他小的题目有关。
• 当 $i$ 结果不可见时，他能否提交只跟编号比他大的题目有关。

因此：

• 当 $i$ 结果可见时，对于每一种选择在他之前的可见的题目 $S$，且满足 $\sum_{j\in S} t_j\le T-t_i$ 的方案，$a_i$ 会产生 $2^{n-i}$ 的贡献。

• 当 $i$ 结果不可见时，对于每一种选择在他之后的可见的题目 $S$，且满足 $\sum_{j\in S}t_j\le T-\sum_{j\le i}t_j$ 的方案，$a_i$ 会产生 $2^{i-1}$ 的贡献。

相当于统计有多少个子集和 $\le$ 一个数。上背包朴素转移，时间复杂度 $O(nT)$。

AC 代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 2e2 + 10;
const int MAXM = 3e5 + 10;
const int mod = 998244353;

int n, m, a[MAXN], t[MAXN];

ll dp[MAXM], p2[MAXM], sum[MAXM], ans, tot;

int main() {
	scanf("%*d%d%d", &n, &m), *dp = *p2 = 1;
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	for (int i = 1; i <= n; i++) scanf("%d", &t[i]), sum[i] = sum[i - 1] + t[i];
	for (int i = 1; i <= n; i++) p2[i] = p2[i - 1] * 2 % mod;
	for (int i = 1; i <= n; i++) {
		tot = 0;
		for (int j = 0; j <= m - t[i]; j++) tot = (tot + dp[j]) % mod;
		ans = (ans + tot * p2[n - i] % mod * a[i]) % mod;
		for (int j = m; j >= t[i]; j--) dp[j] = (dp[j] + dp[j - t[i]]) % mod;
	}
	for (int i = 0; i <= m; i++) dp[i] = 0; *dp = 1;
	for (int i = n; i; i--) {
		tot = 0;
		for (int j = 0; j <= m - sum[i]; j++) tot = (tot + dp[j]) % mod;
		ans = (ans + tot * p2[i - 1] % mod * a[i]) % mod;
		for (int j = m; j >= t[i]; j--) dp[j] = (dp[j] + dp[j - t[i]]) % mod;
	}
	printf("%lld", ans);
}

笑话：看到这题出了我直接去抢首 A，然后由于场外看题没记住数据范围，导致数组开小了两次。