原题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