洛谷P10143 [WC2024] 代码堵塞题解

题目链接：P10143 [WC2024] 代码堵塞

题意：

小 \(\beth\) 为了纪念停办的 codejam，准备了一场“代码堵塞纪念赛”。小 \(\beth\) 的朋友小 \(\mho\) 也来围观，于是小 \(\beth\) 想预测小 \(\mho\) 的成绩。

比赛共 \(T\) 秒，有 \(n\) 道题。第 \(i(1 \le i \le n)\) 题分数为 \(a_i\)，小 \(\beth\) 预测小 \(\mho\) 需要 \(t_i\) 秒完成。

题目有两种类型：结果可见和结果不可见。结果不可见的题在比赛结束后才能知道评测结果，而结果可见的题在提交后立即得到评测结果。小 \(\beth\) 还没确定每道题的类型。

小 \(\mho\) 由于从不写对拍，所以会先按编号从小到大完成所有结果可见的题，再按编号从小到大完成所有结果不可见的题。小 \(\mho\) 会花 \(t_i\) 秒完成第 \(i\) 题，当小 \(\mho\) 花费在第 \(i\) 题和在第 \(i\) 题之前完成的所有题的时间总和不超过 \(T\)，就会在第 \(i\) 题产生提交。

由于小 \(\mho\) 提交即 AC，所以小 \(\beth\) 想知道对于所有 \(2^n\) 种确定 \(n\) 道题类型的方案，小 \(\mho\) 所能得到的分数总和的和。由于答案很大，你需要将答案对 \(998244353\) 取模。

输入格式：

输入的第一行包含三个整数 \(c, n, T\)，表示测试点编号，题数和比赛时间。样例中的 \(c\) 表示其满足的限制条件与第 \(c\) 个测试点一致。

输入的第二行包含 \(n\) 个整数 \(a_1, a_2, \cdots , a_n\)，分别表示每道题的分数。

输入的第三行包含 \(n\) 个整数 \(t_1, t_2, \cdots , t_n\)，分别表示小 \(\mho\) 做每道题的时间。

输出格式：

输出一行包含一个整数，表示对于所有确定 \(n\) 道题类型的方案，小 \(\mho\) 所能得到的分数总和的和，对 \(998244353\) 取模。

数据范围：

对于所有测试数据：

\(1\le n\le 200\)，

\(1\le T\le 3\times 10^5\)，

\(\forall 1\le i\le n , 1\le a_i\le 3\times 10^5\)，

\(\forall 1\le i\le n, 1\le t_i\le T\)。

设 \(f_{i,j}\) 为考虑到 \(i\) ，时间花费为 \(j\) 的方案数。考虑第 \(i\) 道题。

如果 \(i\) 结果可见，小于 \(i\) 的可能在第 \(i\) 道前提交，大于 \(i\) 的不可能在 \(i\) 前提交。

前者实际上为dp统计的方案数，后者只需要乘一个 \(2^{n-i}\) 。

如果 \(i\) 结果不可见，小于 \(i\) 的一定在 \(i\) 前提交，大于 \(i\) 的可能在 \(i\) 后提交。

这与刚才的情况恰好相反，于是我们倒着做一遍dp即可

时间复杂度 \(\mathcal{O}(nT)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int P = 998244353;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
void add(int &x, int y) { (x += y) >= P ? x -= P : 0; }
#define N ((int)(215))
#define M ((int)(3e5 + 15))

int pw[N],a[N],t[N],s[N],dp[M];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int _, n, T; cin >> _ >> n >> T; pw[0] = 1;
    for(int i = 1; i <= n; i++) pw[i] = pw[i - 1] * 2 % P;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) { cin >> t[i], s[i] = s[i - 1] + t[i]; }
    int res = 0; dp[0] = 1;
    for(int i = 1; i <= n; i++)
    {
        int sum = 0;
        for(int j = 0; j + t[i] <= T; j++) add(sum, dp[j]);
        add(res, a[i] * sum % P * pw[n - i] % P);
        for(int j = T; j >= t[i]; j--) add(dp[j], dp[j - t[i]]);
    }
    memset(dp, 0, sizeof(dp)); dp[0] = 1;
    for(int i = n; i; i--)
    {
        int sum = 0;
        for(int j = 0; j + t[i] + s[i - 1] <= T; j++) add(sum, dp[j]);
        add(res, a[i] * sum % P * pw[i - 1] % P);
        for(int j = T; j >= t[i]; j--) add(dp[j], dp[j - t[i]]);
    }
    cout << res << '\n';
    return 0;
}