0215 模拟题解
t1
按照时间 \(dp\)，好处是和活着的怪物个数相关的概率容易计算。
\(dp(i,mask)\) 表示时间到 \(i\)，\(mask\) 的怪已经被干掉的概率。
这里我们假设 \(1\) 到 \(i\) 之间选到 \(mask\) 中的已经被钦定是哪些时间，怎么分配，其他未被钦定。
转移的时候要么干掉一个怪物，要么不干掉，系数都是简单的。
最后还有 \(m-sum(mask)\) 的步数要去选到 \(U\backslash mask\) 中。
这个可以用背包解决。
具体地 \(f(i,mask)\) 表示选了 \(mask\) 中的共 \(i\) 个，顺序已经安排好的方案数。
用去掉 \(lowbit\) 的状态转移过来即可。
时间复杂度：\(O(2^nnm+2^nm^2)\)。
但是最后那个背包可以折半做，优化到 \(O(2^{n/2}m^2+2^nm)\)。
总的时间复杂度还是有 \(2^nnm\)，在前面那个 \(dp\) 里。
空间复杂度：\(O(2^n+2^{n/2}m)\)。
t2
我会猜结论！
阶乘级别复杂度的暴力是容易的，然后可以对于 \(k\le 100\) 打表。
\(n\le10\) 就可以把 \(k\le 100\) 打出来了。
然后观察到 \(k\) 为奇数开头都是 \(2\)，\(k\) 为偶数开头都是 \(1\)。
进一步对 \(k\bmod 4,8,16...\) 找规律，可以写出一个做法。
二进制拆分，从低到高考虑 \(k\) 的每一位，同时维护一个栈和答案序列，以及目前用到了 \(1\) 到 \(m\) 这些数。
如果是 \(1\)，把 \(m+2\) 放入答案序列，\(m+1\) 加入栈顶。
如果是 \(0\)，把栈顶加入答案序列并弹出，假如操作前栈为空，则先把 \(m+1\) 加入栈。
过程中顺便维护 \(m\)。
然后发现过了。
证明也不难证，首先观察操作次数 \(k\) 是怎么来的。
对于每个相邻逆序对 \(a_i,a_{i+1}\)，考虑 \(a_{i+1}\) 之前有 \(c\) 个比 \(a_{i+1}\) 小的数，那么贡献为 \(2^c\)。
接下来贪心地想要去用若干 \(2\) 的整数次幂拼出 \(k\)，容易归纳发现以上过程最优。
时间复杂度：\(O(\log k)\)。
空间复杂度：\(O(\log k)\)。
t3
做法类似 Span Covering 一题，感觉很有启发意义。
首先考虑一些 \(dp\)，但是都无可避免地要去维护整个状态，指数级别显然不行。
\(dp(i,j)\) 表示总共 \(i\) 个黑格子，\(j\) 个连续段，连续段之间间隔 \(\ge 2\)，第一次到达这个状态的概率。
那么我们为什么可以这么维护呢？
首先最开始的状态用连续段来描述可以描述为连续段的长度数组和间隔长度数组。
连续段长度数组不同，其他都相同的状态显然可以合并到一起。
间隔长度数组不同，其他都相同的状态都是等概率的，总概率是这个相等的概率乘上方案数。
所以只需要维护单个的概率即可。
初始值是 \(dp(1,1)=1\)，因为是环，第一步无所谓。
转移是
\[dp(i,j)\times j\times coef\rightarrow dp(i+1,j+1) \ 新开一段\\ dp(i,j)\times 2j\times coef\rightarrow dp(i+1,j) \ 放在一段旁边 \\ dp(i,j)\times 2j\times coef\rightarrow dp(i+2,j)\ 放在一段旁边的旁边 \\ dp(i,j)\times 2j\times coef\rightarrow dp(i+2,j-1) \ 合并间隔为 2 的两段\\ dp(i,j)\times j\times coef\rightarrow dp(i+3,j-1)\ 合并间隔为 3 的两段 \]上述式子中 \(coef\) 的值为 \(\frac 1 {D-i}\)，表示操作一次的概率。
为什么不是 \(\frac 1 D\)？
考虑选已经是黑色的格子，概率是 \(\frac i D\)。
选到另外 \(D-i\) 个中的一个的概率是
\[\frac 1 {D-i}\bigg(\frac {D-i} D+\frac i D\frac {D-i}D+(\frac i D)^2\frac {D-i} D+...\bigg) \]令 \(p=\frac i D\)，后面的式子是 \((1-p)(1+p+p^2+...)=(1-p)\frac 1 {1-p}=1\)。
因此系数就是 \(\frac 1 {D-i}\)。
然后我们对每个不同的状态分别计算贡献。
一个状态 \(dp(i,j)\) 对答案的贡献为
\[dp(i,j)\times i^t\times \binom {D-i-j-1}{j-1}\times \frac D {D-i} \]组合数的系数是把 \(D-i\) 个白格子作为间隔分配到 \(j\) 个里面，每个都至少是 \(2\)。
那么先拿出 \(2j\) 个放好，剩下 \(D-i-2j\) 中插入 \(j-1\) 个板，系数就是这样了。
最后那个系数是，已经在这个状态继续选黑格子的概率是 \(\frac i D\)。
那么贡献是 \(1+\frac i D+(\frac i D)^2+...\)。
令 \(p=\frac i D\)，那么就是 \(\frac 1 {1-p}=\frac D {D-i}\)。
另一种理解方式是，在 \(n\) 个物品中选到 \(m\) 个中的一个的期望步数是 \(\frac n m\)。
所以要 \(\frac D {D-i}\) 步才能选到一个白格子，有 \(\frac D{D-i}-1\) 步不变，再有刚到的一次，加起来共 \(\frac D {D-i}\)。
然后就做完了！
时间复杂度：\(O(n^2)\)。
空间复杂度：\(O(n^2)\)。
标签：概率,frac,复杂度,mask,times,0215,模拟题,dp From： https://www.cnblogs.com/hellojim/p/17127950.html