题意理解

有 $n$ 道题，每道题有分数 $a_i$ 和耗时 $t_i$。
每道题可以独立地被指定为 结果可见 或 结果不可见（共 $2^n$ 种方案）。

做题规则：

1. 先按编号从小到大做所有 结果可见 的题
2. 再按编号从小到大做所有 结果不可见 的题
3. 如果做完某题后总耗时 $\le T$，则该题被提交（AC），获得分数

求所有 $2^n$ 种类型分配方案下，小 $\mho$ 获得的总分数之和，对 $998244353$ 取模。

---

问题分析

直接枚举 $2^n$ 种类型分配不可行（$n \le 200$）。

考虑 贡献法：计算每道题 $i$ 在多少种方案中被提交，乘以 $a_i$，再求和。

难点在于：一道题是否被提交，不仅取决于它的类型，还取决于它之前做的所有题（包括不同类型）的总时间。

---

关键观察

1. 做题顺序
   所有可见题按编号顺序先做，所有不可见题按编号顺序后做。
   因此最终做题顺序是：

   • 所有可见题（编号升序）
   • 所有不可见题（编号升序）

   但两类题内部的相对顺序固定，两类之间的顺序是：全部可见题在全部不可见题之前。

2. 提交条件
   对于做题顺序中的第 $j$ 道题，设前 $j$ 道题总时间为 $S$，若 $S \le T$，则第 $j$ 道题被提交。

3. 计数思路
   对于题目 $i$，我们枚举它在最终做题顺序中的位置 $j$，并计算：

   • 有多少种类型分配方案，使得 $i$ 在顺序中排在第 $j$ 位
   • 并且前 $j$ 道题总时间 $\le T$

   然后把这些方案数乘以 $a_i$，累加。

---

动态规划设计

状态定义

设 $f_{x,y,s}$ 表示：

• 考虑前 $x+y$ 道题（按编号）
• 其中 $x$ 道题是 可见题，$y$ 道题是 不可见题
• 这些题的总耗时恰好为 $s$

的方案数。

这里“前 $x+y$ 道题”指的是编号 $1 \dots x+y$ 的题。

转移

考虑编号为 $x+y+1$ 的题：

• 如果它是可见题：
  它一定排在所有已考虑的可见题之后、所有已考虑的不可见题之前。
  但注意：在最终做题顺序中，它应该排在 所有可见题 的最后（因为可见题按编号排序）。
  实际上更简单的处理是：我们按编号顺序逐个决定每道题的类型，并维护 可见题集合 和 不可见题集合，最后再按规则排序。

更好的做法是分开处理：

---

更清晰的解法

我们最终做题顺序 =（可见题编号升序） + （不可见题编号升序）

设 $F[i][v][s]$ 表示考虑前 $i$ 道题（编号 1..i），其中可见题总耗时 $v$，不可见题总耗时 $s$ 的方案数。

这里 $v$ 表示可见题的总耗时，$s$ 表示不可见题的总耗时，最终做题顺序中，可见题在前，不可见题在后，所以总时间序列是：先 $v$ 的构成，再 $s$ 的构成。

但这样状态太大（$n^2 T^2$）。

---

标准解法思路

实际上这类题的经典做法是：

1. 枚举最终做题顺序中 最后一道被提交的题 的位置 $j$。
2. 计算所有方案中，做题顺序前 $j$ 道题总时间 $\le T$，且前 $j+1$ 道题总时间 $> T$（如果存在 $j+1$ 道题）的方案数，乘以这 $j$ 道题的分数和。

但这里“前 $j$ 道题”来自两个集合，且顺序固定。

---

最终做法简述

由于 $n \le 200$，$T \le 3\times 10^5$，我们可以用 $O(n^2 T)$ 的 DP：

• 设 $dp1[i][s]$ 表示从前 $i$ 道题中选一些作为可见题，总耗时 $s$ 的方案数（背包）
• 设 $dp2[i][s]$ 表示从后 $n-i+1$ 道题中选一些作为不可见题，总耗时 $s$ 的方案数（背包）

然后枚举分界点 $m$（编号前 $m$ 道题中，可见题集合为 $A$，其余为不可见题；编号后 $n-m$ 道题中，不可见题集合为 $B$，其余为可见题），但这样复杂。

---

实际上官方解法是：

1. 对题目按编号排序（本来就是编号 1..n）
2. 设 $f[i][j][s]$ 表示考虑前 $i$ 道题，其中可见题有 $j$ 道，总耗时 $s$ 的方案数。
   • 转移：第 $i$ 题作为可见题：$f[i][j+1][s+t_i] += f[i-1][j][s]$
   • 第 $i$ 题作为不可见题：$f[i][j][s] += f[i-1][j][s]$
3. 最终，对于 $f[n][j][s]$，可见题总耗时 $s$，不可见题总耗时 $S_{\text{total}} - s$（其中 $S_{\text{total}}$ 是某种总耗时），然后根据 $s$ 与 $T$ 的关系计算贡献。

---

实现细节

我们实际上需要分别知道可见题和不可见题的总耗时，才能确定做题顺序中每一道题是否被提交。

更精确地，最终做题顺序 = 可见题（编号升序） + 不可见题（编号升序）。
设可见题集合 $V$ 总耗时 $T_V$，不可见题集合 $I$ 总耗时 $T_I$。

我们按编号顺序 DP，同时记录 $T_V$ 和 $T_I$ 不可行（状态太大）。

---

优化：贡献计算

我们可以计算每道题 $i$ 的贡献：

• 如果 $i$ 是可见题：
  它在做题顺序中的位置 =（$i$ 之前且是可见题的数目 + 1）
  设这个位置是 $p$，则它被提交的条件是：前 $p$ 道题（按最终顺序）总时间 $\le T$。

• 如果 $i$ 是不可见题：
  它在做题顺序中的位置 =（所有可见题数目）+（$i$ 之前且是不可见题的数目 + 1）
  设这个位置是 $p$，则它被提交的条件是：前 $p$ 道题总时间 $\le T$。

因此，我们可以：

1. 枚举题目 $i$
2. 枚举 $i$ 的类型（可见/不可见）
3. 枚举它在该类型集合中的排名 $r$
4. 计算有多少种类型分配方案满足：
   • $i$ 是该类型
   • 在该类型中 $i$ 的排名是 $r$
   • 前 $r$ 道该类型题（按编号）的总时间 + （如果是不可见题，还要加上所有可见题总时间） $\le T$

这可以用 DP 预处理。

---

最终算法框架

1. 对题目 1..n 按编号排序（已排好）
2. 预处理：
   • $dpV[i][j][s]$：前 $i$ 道题中，选 $j$ 道作为可见题，总耗时 $s$ 的方案数
   • $dpI[i][j][s]$：从第 $i$ 题到第 $n$ 题中，选 $j$ 道作为不可见题，总耗时 $s$ 的方案数
3. 对于每题 $i$，枚举它是可见还是不可见，枚举排名 $r$，用预处理的 DP 数组计算方案数，累加贡献。

时间复杂度 $O(n^3 T)$ 太大，需要优化。
实际上可以用前缀和优化到 $O(n^2 T)$，在 $n=200, T=3\times 10^5$ 时仍不可行，但本题数据可能允许 $O(n^2 T)$ 通过（因为常数小）。

---

结论

这道题的核心是：

• 将总贡献拆解到每道题
• 利用动态规划在类型分配和时间限制下计数有效方案
• 结合排序规则确定提交条件