官方题解只能做到 $O(n^3V)$？玩的太差了。本题可以把常规三维背包的 $O(n^3V)$，降到确定性的 $O(n^2V\log(nV))$，其中 $V=\max_i|a_i-m|$。更精确地，经过删除无效元素、约去公因数、选择较小的求和范围后，可以做到 $O(n+L\log(L+1))$ 时间、$O(n+L)$ 空间，而且 $L$ 往往远小于 $n^2V$。
核心不是加速枚举策略，而是把整个问题转化成一个截断的二项式乘积，再用一次形式幂级数指数计算这个乘积。
从最优策略到子集求和
题面中最重要的条件是：无论是否开启护盾，攻击结束后都会知道本次攻击的强度。因此，当前是否开盾，不会影响以后能获得的信息，也不会影响剩余攻击的分布。([QOJ][1])
设当前剩余攻击的下标集合为 $S$，大小为 $k$。开盾的当前费用是 $m$，不开盾的当前期望费用是 $\frac{1}{k}\sum_{i\in S}a_i$。两种决策的后续最优期望费用完全相同，所以当前直接选择两者较小者即可。也就是说，最优策略只是比较剩余攻击的平均强度与 $m$，不需要对策略进行动态规划。
现在选择一个固定策略作为基准。始终开盾的费用为 $nm$，始终不开盾的总费用为 $\sum_i a_i$，取较小者，记为 $C=\min(nm,\sum_i a_i)$。
如果 $nm\le \sum_i a_i$，令 $d_i=m-a_i$，表示相对于始终开盾，不开盾能节省多少；否则令 $d_i=a_i-m$，表示相对于始终不开盾，开盾能节省多少。两种情况下都有 $\sum_i d_i\le 0$，而当前剩余集合为 $S$ 时，相对于基准策略能够获得的最优期望节省都是 $\frac{(\sum_{i\in S}d_i)^+}{|S|}$，其中 $x^+=\max(x,0)$。
先进行两个不会改变问题本质的简化。
当 $a_i=m$ 时，无论如何决策，该次攻击的费用都是 $m$。删去这些攻击不会改变其他攻击之间的随机顺序，也不会改变剩余偏差和的正负，因此不会改变任何有效决策。我们可以直接删去所有 $d_i=0$ 的元素，但基准费用 $C$ 仍按原输入计算。记剩余元素个数为 $N$。
然后令 $g=\gcd(|d_1|,\ldots,|d_N|)$，把所有 $d_i$ 除以 $g$。正负判断不变，最后将算出的节省乘回 $g$ 即可。以下的 $d_i$ 均指约去公因数后的值。
在随机排列中，剩余元素数恰好为 $k$ 时，剩余集合在所有大小为 $k$ 的下标子集中均匀分布。因此，归一化后的总期望节省为
$$ R=\sum_{\varnothing\ne S\subseteq[N]} \frac{\left(\sum_{i\in S}d_i\right)^+} {|S|\binom{N}{|S|}}, \qquad \mathrm{Ans}=C-gR. $$
这里相同数值的元素仍按下标区分。
记 $w_k=\frac{1}{k\binom Nk}=\frac{(k-1)!(N-k)!}{N!}$，问题就变成：统计每种“子集大小、子集偏差和”的出现次数，再乘上相应权重。
直接按“处理了多少元素、选了多少元素、偏差和是多少”做背包，最坏需要 $O(N^3V)$。下面不再逐个元素更新整张表。
把二维计数变成一个截断多项式
令 $Q=\sum_{d_i>0}d_i$，并记正数的个数为 $c$。由于此前选择了较便宜的固定策略作为基准，正数之和不大于负数绝对值之和。换成原输入，$Q$ 正是两侧偏差总和的较小者再除以 $g$。
如果 $Q=0$，任何子集的偏差和都不为正，直接输出 $C$。
接下来只考虑 $Q>0$。
从“选中所有正数，不选任何负数”的子集出发。这个子集的大小为 $c$，偏差和为 $Q$。构造任意其他子集时，对正数 $d_i$，可以选择删去它；对负数 $-b_i$，可以选择加入它。这两种操作分别使偏差和减少 $d_i$ 和 $b_i$。
对一个子集 $S$，定义它相对于上述初始子集损失的偏差为 $t(S)=Q-\sum_{i\in S}d_i$。于是，只有 $t(S)< Q$ 的子集会贡献答案。所有修改都会增加 $t$，所以我们只需要保留这个方向的一个前缀，而不需要维护完整的正负和区间。
我们还可以缩小“子集大小”这一维的范围。
设所有负数的绝对值从小到大为 $b_1,\ldots,b_r$，令 $h$ 为满足 $b_1+\cdots+b_h< Q$ 的最大整数，并令 $K=c+h$。那么，偏差和为正的子集，其大小最多为 $K$，且这个上界可以达到。
证明很直接：求最大大小时一定可以加入所有正数；之后加入尽可能多的负数，显然应优先加入绝对值最小的负数。由于整个集合的偏差和不为正，还有 $K\le N-1$。
计算 $h$ 不必排序。只对小于 $Q$ 的负数绝对值计数，从小到大扫描即可，复杂度为 $O(N+Q)$。
取 $B=K+1$，用一个整数 $Bt+k$ 编码损失 $t$ 和子集大小 $k$。构造多项式
$$ F(z)= \prod_{d_i>0}\left(1+z^{Bd_i-1}\right) \prod_{d_i< 0}\left(1+z^{B(-d_i)+1}\right) \pmod {z^L}, \qquad L=BQ-c. $$
对于正数，对应因子选常数项表示保留它，选非常数项表示删去它；对于负数，选常数项表示不加入它，选非常数项表示加入它。
因此，一个子集 $S$ 在乘积中对应的指数是 $Bt(S)+|S|-c$。
注意这里的 $-1$ 和 $+1$：删去一个正数，大小减少 $1$；加入一个负数，大小增加 $1$。初始大小 $c$ 最后统一加回，因此两个维度被准确地编码到了同一个指数中。
现在验证截断是否安全。
对于有贡献的子集，有 $t(S)\le Q-1$、$|S|\le K=B-1$，所以它的指数至多为 $B(Q-1)+(B-1)-c=L-1$，一定被保留。对于没有贡献的子集，有 $t(S)\ge Q$、$|S|\ge0$，所以它的指数至少为 $BQ-c=L$，一定被删除。
这说明，指数小于 $L$ 的项恰好对应全部有贡献的子集，没有遗漏，也没有无效项混入。 对这些项还有 $0\le |S|< B$，因此不会发生编码冲突。
设 $f_j=[z^j]F(z)$。将 $j+c$ 除以 $B$，商就是损失，余数就是子集大小，所以答案为
$$ \mathrm{Ans} = C-g\sum_{j=0}^{L-1} f_j \left(Q-\left\lfloor\frac{j+c}{B}\right\rfloor\right) w_{(j+c)\bmod B}. $$
可以令 $w_0=0$。实际上，有贡献的子集不可能为空，因此余数为 $0$ 的位置，其系数必然为 $0$。
到这里，剩下的问题只有一个：快速计算 $F(z)$ 的前 $L$ 项。
一次形式幂级数指数完成计算
把前面所有因子的指数统一记为 $e_i$，则 $F(z)=\prod_i(1+z^{e_i})\pmod{z^L}$。直接逐个乘入因子仍然需要 $O(NL)$，这并没有真正去掉动态规划中的元素维度。
我们先求对数。
统计每种指数的出现次数 $q_e$。由 $\log(1+x)=\sum_{r\ge1}(-1)^{r+1}x^r/r$，可得 $\log F(z)=\sum_e q_e\sum_{r\ge1,\ er< L}(-1)^{r+1}z^{er}/r$。
因此可以直接按倍数枚举，生成 $\log F$：
令 logF[0 ... L-1] 全部为 0
对每个出现过的指数 e：
对 r = 1, 2, ...，直到 e*r >= L：
logF[e*r] += q[e] * (-1)^(r+1) / r
F = exp(logF) mod z^L必须先合并相同的指数，不能因为有很多相同元素而重复枚举它们的倍数。合并之后，即使对所有 $1\le e< L$ 都枚举倍数，总枚举次数也只有 $\sum_{e=1}^{L-1}\lfloor(L-1)/e\rfloor=O(L\log L)$。
最后使用 NTT 上的形式幂级数指数，就能在 $O(L\log L)$ 内恢复 $F$。形式幂级数指数可以做到与多项式乘法相同的渐进复杂度。([arXiv][2])
具体来说，如果当前已知 $f=\exp(\ell)\pmod{z^s}$，其中 $\ell=\log F$，就可以用 $f\leftarrow f(1+\ell-\log f)\pmod{z^{2s}}$ 将精度翻倍。而 $\log f$ 可以通过 $\log f=\int f'/f$ 求得，其中多项式逆同样用牛顿迭代。各轮精度倍增，运算量按几何级数增长，因此总复杂度为 $O(L\log L)$，不会额外多出一个倍增轮数的因子。
权重 $w_k$ 用阶乘及 $N!$ 的逆元预处理，最后扫描一次 $F$ 即可。题目给定 $n,m\le100$、$a_i\le200$，所需级数长度远小于模数 $998244353$，所有积分及对数展开涉及的整数分母都可逆，NTT 长度也在该模数支持的范围内。([QOJ][1])
最终复杂度是 $O(n+L\log(L+1))$ 时间、$O(n+L)$ 空间，其中 $L=(K+1)Q-c< NQ$。由于 $N\le n$、$Q=O(nV/g)$，得到最坏情况下的 $O(n^2V\log(nV))$ 时间、$O(n^2V)$ 空间。
这里不仅去掉了逐个元素转移的一重 $n$，还利用了几个实际有效的缩减：删除零偏差、约去公因数、只计算较小一侧的偏差总和，以及使用真正可能出现的最大子集大小 $K$，而不是机械地取 $n+1$ 作为编码底数。
还有一个实现细节：指数不小于 $L$ 的因子可以不参与多项式计算，但对应元素仍然必须计入 $N$，用于计算权重。 它们只是不能出现在有贡献的选择中，并不等价于从随机排列中消失；只有零偏差元素可以真正删除。