$$【组合数学】专题笔记目录$$

被标题 WC2024 吓到了，这题的思想其实很巧妙也很好理解。冬令营最水的一题。
最朴素的想法：$2^n$ 枚举每一道题是 IOI 还是 OI 赛制。
然后考虑对每一道题讨论它对答案的贡献，即它能在多少种状态下获得该题分数。

先考虑这一题是 IOI 赛制。
观察到这一题能否被完成取决于它前面的 IOI 赛制题目是否能完成。
则设 $f_{i,j}$ 表示前 $i$ 题，剩下 $j$ 的时间，完成所有 IOI 赛制题目的方案数。
这可以用 01 背包处理，转移方程为 $f_{i,j} = f_{i-1,j} + f_{i-1,j-t_i}$。可以压掉其中一维。
第 $i$ 题作为 IOI 赛制的贡献即为 $a_i \times f_{i,T-t_i} \times 2^{n-i}$。

再考虑这一题是 OI 赛制。
观察到这一题能否被完成取决于它前面的所有题目和它后面的 IOI 赛制题目是否能完成。
设 $g_{i,j}$ 表示后 $i$ 题，剩下 $j$ 的时间，完成所有 IOI 赛制题目的方案数。
这也可以 01 背包处理，转移方程为 $g_{i,j} = g_{i+1,j} + g_{i+1,j-t_i}$。也可以压掉其中一维。
第 $i$ 题作为 OI 赛制的贡献即为 $a_i \times f_{i,T-t_i-sum} \times 2^{i-1}$。

直接背包转移并统计答案即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 15, M = 215;
const int mod = 998244353;
int id, T, n;
int a[M], t[M];
int f[N], g[N];
long long ans = 0;

int qmi(int a, int k) {
    int res = 1;
    while (k) {
        if (k & 1) res = (res * 1ll * a) % mod;
        a = (a * 1ll * a) % mod;
        k >>= 1;
    }
    return res;
}

int main() {
    scanf("%d%d%d", &id, &n, &T);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &t[i]);
    for (int i = 0; i <= T; i++) f[i] = g[i] = 1;
    for (int i = 1; i <= n; i++) {
        ans = (ans + a[i] * 1ll * f[T - t[i]] % mod * 1ll * qmi(2, n - i) % mod) % mod;
        for (int j = T; j >= t[i]; j--) {
            f[j] = (f[j] * 1ll + f[j - t[i]] * 1ll) % mod;
        }
    }
    int sum = 0; for (int i = 1; i <= n; i++) sum += t[i];
    for (int i = n; i >= 1; i--) {
        sum -= t[i];
        if (sum + t[i] <= T) {
            ans = (ans + a[i] * 1ll * g[T - sum - t[i]] % mod * 1ll * qmi(2, i - 1)) % mod;
        }
        for (int j = T; j >= t[i]; j--) {
            g[j] = (g[j] * 1ll + g[j - t[i]] * 1ll) % mod;
        }
    }
    printf("%d\n", ans);
    return 0;
}