原题link
把 \(m\) 和 \(a_i\) 的上界改成 \(200\)，其他不变.
基本思路：枚举 \(S\)，求出 \(p(S)\) 表示集合 \(S\) 中的怪兽被打死的概率，答案就是 \(\sum_{S} |S|p(S)\).
而这个集合 \(S\) 满足一些性质，具体来说对于 \(x \in S\), 它恰好被攻击了 \(a_x\) 次，而对于 \(x \notin S\), 它至多被攻击了 \(a_x-1\) 次. 这启发我们把 \(p\) 拆成两个部分，第一部分计算 \(S\) 中恰好被打死的概率，第二部分计算 \(S\) 以外的没被打死的方案数，注意在第一部分中计算的是所有等概率情形，所以第二部分要计算方案数.
具体的，来说，考虑如下的 \(dp\).
我们考虑一个长度为 \(m\) 的攻击序列 \(j_1, j_2, \cdots, j_m\) 表示每次被攻击的怪兽的编号，那么一个显然的 dp 是说，设 \(f(s, i)\) 表示考虑前 \(i\) 次攻击（即 \(j_1, j_2, \cdots, j_i\)）已经打死了 \(S\) 集合中的怪兽，概率是多少.
考虑如何转移这个 \(f\).
为了简便，我们记 \(w(S)=\sum_{x \in S}a_x\).
考虑第 \(i\) 次攻击，是正好杀死了一个怪兽还是打在了别的地方。
第一种情况是说我们不确定位置（相当于等概率随机），那么直接乘上概率转移即可, 即 \(f(S, i - 1) \frac{1}{n - |S|}\).
第二种情况是我们枚举最后一次杀死了集合 \(S\) 中的一个元素 \(v\), 则是从 \(f(S \backslash \{v\}, i - 1)\) 转移过来的. 首先要乘上对应的概率系数 \(\frac{1}{n-|S \backslash \{v\}|}=\frac{1}{n-|S|+1}\)，表示在这些怪兽中正好打到了这一个，但是还有一个限制是说在这之前，\(v\) 这个怪兽应该只剩一滴血了，那么我们在前面的攻击序列中需要找出 \(a_v-1\) 个位置来打 \(v\) 使得 \(v\) 只有一滴血，而前面的 \(i - 1\) 长度的攻击序列中，有一部分是必须用来打 \(S\backslash\{v\}\)，剩下的才是自由的，所以这个系数就是 \(i - 1 - w(S \backslash \{v\}) \choose a_v-1\) .
对于第二种情况的理解：一开始看到可能觉得奇怪，为什么限制 \(v\) 怪兽只剩一滴血反而还要乘上一个系数使概率变大了，其实这个是比较显然的，我们在 \(f(S\backslash\{v\}, i - 1)\) 中只考虑了 \(S\backslash\{v\}\) 被打死之后的所有等概率情形的概率，而在限定了 \(v\) 这个怪兽只有一滴血后，我们的情形变多了，因为在所有的等概率情形中，有 \(i - 1 - w(S \backslash \{v\}) \choose a_v-1\) 种都满足 \(v\) 这个怪兽只剩一滴血的限制.
于是可以列出转移式子如下：
\[f(S, i) = \frac{1}{n - |S|}f(S, i - 1) + \frac{1}{n-|S|+1}\sum_{v} f(S\backslash\{v\}, i - 1)\binom{i - 1 - w(S\backslash\{v\})}{a_v-1} \]直接暴力转移 \(f\)，时间复杂度是 \(O(2^nnm)\) 的.
现在要求剩下的方案数了，我们相当于要用 \(m-|S|\) 个数表示剩下的怪兽，给剩下的长度为 \(m-w(S)\) 的攻击序列染色，第 \(i\) 种颜色有一个上界 \(a_i-1\)，染色表示的是这次攻击打给了哪个怪兽，就染对应的颜色.
这其实是一个背包，具体地，我们可以这样计算，设 \(g(S, i)\) 表示有 \(i\) 次攻击在 \(S\) 中并且 \(S\) 中一个没死的方案数，注意这里概率我们已经求出了，剩下的是计算没有确定的位置有多少方案，所以设的是方案数. 而 \(g\) 的转移比较显然，我们可以钦定 \(S\) 中的某个元素来转移，不妨钦定最大的是 \(v\)，那么就要枚举有 \(j\) 次攻击打到了 \(v\) 身上进行转移，式子如下：
\[g(S, i)=\sum_{j=0}^{\min(a_v-1,i)}{i \choose j}g(S\backslash\{v\},i-j) \]注意 \(min(a_v - 1, i)\) 是说打在 \(v\) 上的攻击不能超过 \(a_v-1\)，否则会杀死 \(v\)，并且不能超过 \(i\)，因为总共就 \(i\) 次攻击.
最终用 \(f\) 和 \(g\) 配合，求出答案：\(\sum_S |S| f(S, m)g(\overline S, m-w(S))\).
还有最后一个问题，暴力转移 \(g\) 的复杂度是 \(O(2^n m^2)\) 的，这东西大于 \(10^9\)，我们考虑优化这个转移.
可以使用 meet in the middle 的技巧，我们先暴力计算 \(S\) 的前 \(n/2\) 位和后 \(n/2\) 位，称为 \(g_1,g_2\)，这样的复杂度是 \(O(2^{n/2}m^2)\) 的.（前表示高位，后表示低位）
考虑设 \(S\) 的前 \(n/2\) 位是 \(x\)，后 \(n/2\) 位是 \(y\)，则 \(g(S,i)=\sum_{j+k=i}g_1(x,j)g_2(y,k)\binom{i}{j}\).
换句话说，我们可以以 \(O(m)\) 的代价合并对于某个特定 \(g(S, i)\).
注意到我们只关心 \(g(\overline S, m-w(S))\). 可以用 \(O(2^n m)\) 的复杂度处理出这些 \(g\) 的值，然后统计答案即可.
最终复杂度是 \(O(2^nn+2^n nm+2^{n/2+1}+2^nm+2^n)\)，分别是算 \(w\)，算 \(f\)，算 \(g1, g2\)，算 \(m\) 个特定的 \(g\)，统计答案.
差不多是 \(O(2^n nm)\)，这个是 \(10^8\) 的.
总结：
这个题核心在于把 \(p\) 拆成 \(f*g\)，\(f\) 是满足约束情况下的概率，\(g\) 则是剩下部分的方案数，这种思想在 \(f\) 的转移中的第二种情形也有所体现，建议读者仔细体会.
标签：怪兽,概率,CCPC2020,攻击,题解,sum,backslash,转移,Gym102798 From： https://www.cnblogs.com/chengchunhao/p/16587633.html