1.ARC101E
link && submission
一直认为容斥都是人类智慧题
容斥！定义 f[s] 表示 s 集合内部的边一定没有被染色。那么答案就是 \(\sum (-1)^k f[s]\)，其中 k 是 s 的 size。
没有染色说明什么？不妨假设一条边 \(i \in s\) ，那么它连接的两个点肯定是不联通的。这里联通的定义是不能通过不在 s 里的边到达。
因为这里我们不用管每个联通块内部的状态，只需要求出每组容斥对应的状态，所以定义 g(i) 表示大小为 i 的连通块任意配对的方案数。如果 i 是奇数那么 g(i)=0，否则 $g(i)=\prod \limits_{j=1} ^{\frac{i}{2}} (2j-1) $ 考虑意义的话就是你每次考虑把当前没有染色过的最小的点拿出来，再为其随便选一个点。
考虑 dp 。定义 dp[i][j] 子树 i 内节点 i 所在的连通块大小为 j 的容斥系数。答案就是 \(\sum dp[1][i] \times g(i)\)。
现在来看怎么转移。如果当前枚举这条边不断掉，那么就是一个树形背包；如果当前这条边断掉了？由乘法原理得 \(dp[x][i] \leftarrow - dp[x][i] \times dp[y][j] \times g(j)\) 因为是容斥所以有负号，你相当于是在把很多个子集一起算。
然后做完了。
2.CF1854C
link && submission
发现自己是概率垃圾数学垃圾信竞耻辱/kk/kel/wq/ll/dk
把数轴上初始存在的数看作关键点，首先根据期望的线性，我们将问题转换成每一个点被删去的期望步数。然后我们把一个点追逐上另一个点之后的过程看作删去追逐另一个点的那个点，也就是两点中靠前的那个点。
定义 dp[i][j] 表示追逐的点初始位置在 i，被追逐的点初始位置在 j 时删去追逐的点的期望步数。这样定义的好处是我们不用考虑数轴上 i 之前的点发生了什么。只考虑这一对点，每个点都有一半的概率被选中。那么 $dp[i][j] = \frac{1}{2}(dp[i+1][j] +1) + \frac{1}{2} dp[i][j+1] $。
最终的答案是 \(m-s_n+1 + \sum\limits_{i=1}^{n-1} dp[s_i][s_{i+1}]\) 。
3.AGC023F
link && submission
想到了很久以前想对 kww 说的一句话：你就像一棵树的根节点！
如果我们可以随便选点，那么最优的方案就是排成 00000111111 但是这道题并不像 kww 一样脑瘫。考虑怎么把问题往 kww 上面靠。发现最后的序列一定是在上述序列上选择了几对 01 交换位置。那么在选点的时候我们先把 0 选了无论如何都是不亏的，所以如果一个权值为 0 的点一旦可以选就一定会被选。我们考虑把这个信息和他父亲合并。然后把信息放在优先队列里面实时更新就做完了。
4.CF1515E
link && submission
这道题我真做过？哦去年做的啊那没事了。开胡！
如果所有电脑都是自己手动打开的一共有多少种方案数？枚举第一个打开的电脑，接下来分别有 \(\binom{n-1}{0},\binom{n-1}{1},……\binom{n-1}{n-1}\)，共有 \(2^{n-1}\) 种选择方式。然后发现两堆手动打开的电脑中间最多夹一个自动打开的。利用这个性质分段然后 dp。 定义 dp[x][y] 表示前面 i 个电脑打开了，其中手动打开了 j 台电脑的方案数。那么转移显然是 \(dp[i+1+k][j+k]=dp[i][j]×2^{k-1}×C[j+k][k]\) 然后就做完了。时间复杂度 \(\mathrm{O(n^3)}\) 的。
看看代码。我抄的哪篇题解啊根本不对啊。
哦，连续段 dp！这下听懂了。
在一类序列计数问题中，状态转移的过程可能与相邻的已插入元素的具体信息相关。我们将整个序列通过还未插入数字的位置分成若干个连续段，那么显而易见的每次往空位置插入数字将会对当前的连通块状态产生三种影响，第一种是在中间多一个连续段，第二种是合并两个连续段，第三种是延长一个连续段。理解 连续段dp 的难点在于如何考虑其所谓的 “不需要考虑两个连续段之间的绝对位置”，只需要考虑其相对位置。
为什么这个是对的？因为你每次插入一定能对应原序列的一种插入方案。不存在插入方案也就不存在转移了。所以一定是对的。
然后我的代码就很好理解了。但是一般来说此类 dp 应该去刷表来做，会清晰很多。但是我做这道题的时候被 kww 附身了，脑瘫了。
5.CF908D
link && submission
推式子题。但是我不想推怎么办呢。
他要什么我就设什么，定义状态 dp[i][j] 表示当前至少有了 i 个 a，j 个 ab 的期望步数。很明显的状态转移式 \(dp[i][j]=A\times dp[i+1][j] + B \times dp[i][j+1]\)，其中 \(A/B\) 表示下一步选择 a/b 的概率。答案为 dp[1][0]（因为一开始你随机出来多少个b都不影响最终 ab 的个数）。
然后推式子推出来的东西大概是：当 \(i+j \geq k\) 的时候，\(dp[i][j]=i+j+\frac{pa}{pb}\)。
这个推起来很麻烦！大概就是你考虑当前已经达到了 \(i+j+1=k\) 的时候，下一步如果选择了 b 那么就停止了，否则就会多一对 ab。所以期望可以写成 \(\sum\)