A
有 \(n\) 个人，血量为 \(a_i\)，\(m\) 次攻击，每次随机选一个血量不为 \(0\) 的人使其血量减 \(1\)，问期望使多少人血量归零。\(n\le 15,a_i,m\le 200\)。
设 \(dp_{i,s}\) 表示前 \(i\) 次攻击 \(s\) 集合里的人已经死了，此时的贡献。
转移的话，枚举一个在此时全部死掉的一个人，再把这个人分配空位进去即可。
枚举上一个死人的点，设这一段长度为 \(k\)，那么这一段的系数贡献是 \((\frac{1}{n-|s|+1})^k\)。
最后还需要把没死的人分配进空位里面去，直接做背包是 \(O(2^nm^2)\)，考虑 EGF 优化？
优化这一步的话考虑 meet in middle 即可。
B
一种排序方法是重复以下过程：从前往后找到第一个 \(a_i>a_{i+1}\)，将后者移动到第一位。
请构造字典序最小的一种排列使得其所需的步数为 \(k\)，\(k\le 10^{18}\)。
考虑拆贡献，注意到每个不为前缀 \(\max\) 的位置的数的贡献是 \(2^x\)，\(x\) 为前面比其小的数的个数。
拆成二进制的形式其实很典。
那么我们就有了一种构造：维护当前最小未填的数 \(L\)；以及一个栈。
考虑从 \(k\) 二进制的低位开始构造，如果为 \(0\)，那么就填入当前栈顶。如果栈空就填最小 \(L\)。
那么此时就将 \(k\) 右移一位即可，后面每个数都会有 \(\times 2\) 的贡献，也就是可以把前面已填的数给忽略掉。
如果最后一位为 \(1\)，那么就填 \(L+1\)，这样 \(L\) 的贡献就是 \(1\)，同时把 \(L\) 加入栈，并将 \(k\) 右移一位。
栈的含义就是里面的数的贡献都要是 \(1\)，也就是前面不能有比其小的数。