0215测试
0215测试
T1
期望题的统计方式有很多，主要有以下几种：
枚举可能的最终状态，计算其概率和权值并加和。
- 对于每种基本情况概率相同的，可以直接总答案除以总情况。
考虑状态转移每一个过程的贡献和取到该过程的概率，用期望线性性加和。
正向动态规划，记录期望值和概率值。
反向动态规划，记录该状态到终末状态的期望。
其中方式 3 的本质和方式 2 相同，但一般情况更为麻烦，只是便于初学时理解，方式 2 相比于方式 3 显然更加强大，因为不需要拘泥于转移的过程，只需要计算取到某个状态的概率值。
注意到这道题的基本情况概率不等，所以不能简单的算方案数来计算答案。
方式1
设 \(dp[mask][k]\) 表示第 \(k\) 步杀了人，被杀状态为 \(mask\) 的概率，发现转移比较困难，更改定义为 \(dp[mask][k]\) 表示到达该状态的且只考虑 \(mask\) 这些人的位置的情况下的权值和，容易发现概率就是权值和乘以考虑剩下的人的方案数。
转移就是一个前缀和的形式。
也可以就定义状态为概率，转移考虑计算先验概率，确定先决条件之后，考虑将所有选的不是 \(mask\) 的步骤拿出来，在合法的前提下，这些就是等概率选择。可以直接计算合法方案数，而样本空间的方案数则是 \(cnt\times r^{k-j}\)，其中 \(cnt\) 代表合法走到上一步的方案数。
方式2
其核心仍然是计算取到一个状态的概率，本质和方式一相同。
方式4
需要计算从一个状态转移到另一个状态的概率，本质和方式一相同。
T2
这个排序肯定要先排好一个前缀的序才能排下一个，所以考虑 \(W(n,k)\) 表示前面有 \(n\) 个数且已经有序，第 \(n+1\) 个数在总共前 \(n+1\) 个数的排名为 \(k\)，将前 \(n+1\) 个数排好需要的次数。
容易发现第一次交换之后问题转化为了求第 \(k\) 个数在第一个，排好序的次数，此时答案和 \(n\) 无关了，因为只有前 \(k\) 个数涉及到逆序对，记此时的答案为 \(S(k)\)。
写出 \(S(k)\) 的递推式： \[ S(k)=\sum_{i<k}(S(i)+1) \] 用前缀和捣鼓一下，再弄个生成函数算算通项公式，发现 \(S(k)=2^k-1\)，自然 \(W(n,k)=2^k\)。
于是给一个排列算交换次数就好办了，考虑怎么构造。
有解的构造
首先一定有解，方法是先放一个很大的，然后由低到高考虑每个二进制位，如果存在就放到排列最后面，不存在就放到排列的最前面，这样能构造出一种合法的方案。
套路的构造
枚举下一个位置的最小值，考虑能不能行。
前面已经确定了，所以剩下的数贡献的最小值也确定了。同样的道理把一个很大的放到当前的前面，接着由小到大考虑放。每一个数的可行范围下界是前面确定的比它小的数的个数，取到下界很容易，逆序放即可。我们证明上界可以无穷大。构造方式也是简单的，设确定的最大值为 \(m\)。如果这个数小于 \(m\)，找到前面确定第一个大于它的数并替换掉。取值变大 \(1\)，如果此时不小于 \(m\)，一定可以插入到一个不改变 \(k\) 值的位置使得它不贡献继续考虑下一个数。
所以检查可以直接看当前 \(k\) 的每一位是否都能构造来。
由于答案不会太长，所以 \(O(n^3)\) 没问题。
奇妙的构造
如果 \(1\) 填到了最前面，那么答案一定是偶数，然后如果能构造出一个答案为 \(\frac{s}{2}\) 的，那么把答案为 \(\frac{s}{2}\) 的排列所有元素加一并把 \(1\) 再放到前面就是最小的字典序。
如果 \(s\) 此时是奇数，那么可以把 \(2\) 放到最前面，此时只要把 \(1\) 放到最后面，一定可以再按照那个有解的构造弄一个出来。
然后已知 \(1\) 在 \(2\) 后面了，一定会贡献一个 \(1\)，然后继续考虑 \(\frac{s}{2}\)，此时如果末尾为 \(0\) 了，可以把先前的 \(1\) 拿过来补上去会更小。注意这是递归的构造，先前的最小值可能有多个，一定要拿最大的拿一个补上去，否则后面更大的有一位是不对的。
T3
考虑设 \(dp[i][x]\) 表示还剩 \(i\) 天不是假期，一共有 \(x\) 段的概率以及期望贡献，转移的时候发现信息不够，因为要考虑每一段的长度这些。
于是采用第一题提到的第二种方式，考虑设计一些状态，计算这些状态转移到下一个状态的期望权值并计算取到这些状态的概率，用期望的线性性质加和。
这里设 \(cnt[x][y]\) 表示有 \(x\) 天是某个继任者的生日，\(y\) 天由于相邻两天是假期被设成了假日的方案总数。由于每种基本情况概率相等，所以出现这种情况的概率显然是 \(\frac{cnt[x][y]}{\binom{n}{x}}\)，从这种状态转移到下种状态的期望也是好算的。
现在的问题变成了求 \(cnt[x][y]\)。考虑将一种合法视为 012 串，0 不是假期，1 是继任者的生日，2 不是继任者的生日但是是假期。有一个简单的 \(O(n^3)\) 动态规划可以做它，但是还不够。可以把一段连续的 12121 视作一段，于是就变成了 01 串，由于知道总长度，所以只需要将多余的长度划分给每个 1 就能算出总方案数。
问题变成了 01 串，比较好做了。把链拼成环时可以假定第一天是第一任的生日，分第一天前面是否为 2 讨论。
本质上，我们最初要求三维空间中一个平面的值，然后其实中间过程是没用的，只需要知道那个平面上每个点的值，通过一些性质我们把平面拿了出来单独算，于是就 \(O(n^2)\) 了。
对第一种动态规划可以运用相同的考察方式，可以注意到每个状态的基本情况概率相等。于是就可以分类讨论算下个状态的概率了。