有史以来最水的 T4，我都会做。
形式化题面
给定一个长 \(n\) 的序列 \(\{a_i\}\)（\(1\le n ,a_i \le 5000\)），你需要找到一个长度为 \(m\) 的子序列，记下标为 \(b_1,b_2,\dots,b_m\)，满足：
-
\(m\ge 3\)
-
\(\sum_{i=1}^{m} b_i > 2 \times \max_{i=1}^{m} b_i\)
求满足条件的子序列 \(b\) 的数量，答案对 \(998244353\) 取模。
测试点信息:
::cute-table{tuack}
| 测试点编号 | \(n \leq\) | \(\max_{i=1}^{n} a_i \leq\) |
|---|---|---|
| \(1 \sim 3\) | \(3\) | \(10\) |
| \(4 \sim 6\) | \(10\) | \(10^2\) |
| \(7 \sim 10\) | \(20\) | ^ |
| \(11 \sim 14\) | \(500\) | ^ |
| \(15 \sim 17\) | ^ | \(1\) |
| \(18 \sim 20\) | \(5\,000\) | ^ |
| \(21 \sim 25\) | ^ | \(5\,000\) |
思路
考虑到这个 \(\max\) 很烦，我们想到把它搞掉，自然想到把 \(\{a_i\}\) 从小到大排序。
然后我们只要枚举最大值 \(a_i\)（\(1\le i\le n\)，注意这个是强制选择 \(a_i\)），相当于就是要求有多少个由 \([1 ,i - 1]\) 内的数组成的非空下标子集 \(S\)，使得:
即：
但是这里不用考虑 \(m\ge 3\)。
:::info[原因]{open}
显然 \(m = 1\) 就是只选择 \(a_i\) 一个数，那么肯定不满足 \(0 > a_i\)。
当 \(m = 2\) 时相当于要找 \(1\le j < i\) 使得 \(a_j > a_i\)，由于我们是升序排序，这个自然也不可能。
综上所述，\(m\) 的限制我们可以不用考虑。
:::
现在我们的流程如下：
-
计算前 \(i - 1\) 个数所有的非空子集的和大于 \(a_i\) 的数量。
-
把第 \(i\) 个数的贡献加上。
具体地，我们设 \(f_{i ,j}\) 为前 \(i\) 个数，凑出和为 \(j\) 的方案数，记答案为 \(ans\)，那么每次统计答案（\(i\ge 3\)）相当于：
其中 \(V = \sum a_i\)，也就是所有数的和。
然后加上第 \(i\) 个数的贡献为：
前面的是不选择 \(a_i\)，后面的是选择 \(a_i\)。
初始化 \(f_{0 ,0} = 1\)。
时间和空间复杂度都为 \(\mathcal O(nV)\)，其中 \(V\) 为 \(\mathcal O(n\times a_i)\) 级别（由于 \(n\) 和 \(a_i\) 同价，此处和下文默认为 \(\mathcal O(n^2)\) 哦），也就是 \(\mathcal O(n^3)\)。
CCF 非常良心，给了几个 \(\max\limits_{i = 1}^n a_i = 1\) 的数据，这样 \(\sum a_i\) 就是 \(n\)，时间复杂度为 \(\mathcal O(n^2)\)。
注意到这边空间复杂度有点高，我们压缩一下，转移就为：
这边 \(j\) 倒着枚举，\(f_j\) 对应上文 \(f_{i -1 ,j}\)，\(f_{j - a_i}\) 对应上文 \(f_{i - 1 ,j - a_i}\)，空间复杂度为 \(\mathcal O(n^2)\)。初始化 \(f_0 = 1\)。
期望和实际得分都是 \(80\)。
namespace lolcrying {signed main(){n = read();int sum = 0 ;up(i ,1 ,n) a[i] = read() ,sum += a[i];sort(a + 1 ,a + 1 + n);f[0] = 1;up(i ,1 ,n) {if(i >= 3) {up(j ,a[i] + 1 ,sum) ans += f[j] ,ans %= mod ; }dn(j ,sum ,a[i]) f[j] += f[j - a[i]] ,f[j] %= mod;}writeln(ans);return 0 ;}}
然后考虑正解。
我们发现这样做转移和统计答案都会 TLE，于是考虑优化（废话）。
观察到统计答案部分，我们自然想到用前缀和，即 \(\sum\limits_{i = 1}^{sum} f_i - \sum\limits_{i = 1}^{a_i} f_i\)。
我们又想，此时如果可以快速计算前面的部分，后面的部分值域就是 \(a_i\)（\(5000\)），这样转移也不用这么费时了。
仔细一想，发现前面部分真的可以 \(\mathcal O(1)\) 算，具体地，我们转化一下，前面就是总方案数。
那么总方案数就是前 \(i - 1\) 个数随便取或不取，去除空集，数量为 \(2^{i - 1} - 1\)，前面可以快速幂做到 \(\mathcal O(\log mod)\)，或者循环的时候直接做 \(\mathcal O(1)\)。
然后转移和统计答案都是 \(\mathcal O(n^2)\) 了！
这种思想好像是正难则反。
这样，我们通过了 CSP-J 2025 T4（皆大欢喜）。
期望和实际得分都是 \(100\)。
:::success[实现]{open}
namespace lolcrying {inline int qpow(int a ,int b){int res = 1;for( ; b ; a = a * a % mod ,b >>= 1) if(b & 1) res = res * a % mod;return res;} signed main(){n = read();up(i ,1 ,n) a[i] = read();sort(a + 1 ,a + 1 + n);f[0] = 1;up(i ,1 ,n) {if(i >= 3) {int total = 0 ;up(j ,1 ,a[i]) total += f[j] ,total %= mod; // 不合法数量。ans += (qpow(2 ,i - 1) - 1 - total + mod) % mod ,ans %= mod; // 总量 - 不合法数量。}dn(j ,5000 ,a[i]) f[j] += f[j - a[i]] ,f[j] %= mod; // 转移。}writeln(ans);return 0 ;}}
:::
其余无启发性子任务
-
\(n\le 20\) dfs 暴力。
-
\(a_i \le 1\) 你能发现任何 \(m \ge 2\) 的子序列都成立，答案即为 \(\sum\limits_{i = 3}^n \binom{n}{i} = 2^n - 1 - n - \frac{n(n - 1)}{2}\)。
-
其余不知道，但是都能用 \(80\) 的 DP。