DP 与集合幂级数做题记录

Max Correct Set

证明 周期

改成从$0, \ldots, n-1$中选择数也是等价的。

本题的难点在于证明：存在一种最优解使得其周期为$x+y$。

有了这个就可以写一个状圧 DP：$f(i, S)$表示考虑在$0, 1, \ldots, i-1$中选一个合法的集合，其中最后的$\max(x,y)$个数的选择状态是$S$的最优解。

记$c_i$表示$0, \ldots, n-1$中$\bmod {(x+y)}$为$i$的数的个数。用这个辅助 DP 的转移即可。

代码

Neko Rules the Catniverse

状圧 矩阵乘法

不妨把条件改成$y\ge x-m$。

设$f(i, j, S)$表示考虑了$1, \ldots, i$，序列长度为$j$，且$i, i-1, \ldots, i-m+1$的使用状态是$S$的方案数。

每次转移要么不选$i+1$，要么把$i+1$放到序列末尾，要么放到某个数$x$的前面（$x \ge i-m+1$）。

然后使用矩阵乘法优化静态转移即可。

时间复杂度$O((k2^{m+1})^3\log_2 n)$。

代码

The Celebration of Rabbits

FWT

由于序列长度是奇数，因此对于一个序列最多有$1$个$x$使得其异或和为$0$。因此我们可以枚举$x$，把值域变成$[x, m+x]$。这样问题就转化成$2n+1$个数异或和为$0$的方案数。直接 FWT 即可。

做这题的时候这 OJ 好像出问题了。不保证代码正确性。

代码

Bank Security Unification

DP 缩减状态

我们用$a_i$表示题目中的序列。

朴素的 DP 是设$f(i)$表示前$i$个数的答案。暴力转移的复杂度是$O(n^2)$的。

考虑缩减状态。设$H(x)$表示$x$的最高位。那么对于以$a_i$结尾的最优解$a_{j_1}, a_{j_2}, \ldots, a_{j_k}, a_i$，一定不存在$j_k < j^\prime < i$，使得$H(a_{j_k}\&a_{j^\prime}) = H(a_{j^\prime}\&a_i)$。否则我可以把$j^\prime$加进来使得答案更大。

根据上述发现，我们可以设$t_i$表示最大的$j$使得$a_j$的第$i$位为$1$。那么对于$f(i)$只需要考虑所有的$t_j$作为转移即可。

时间复杂度$O(n\log_2w)$。

代码

随机二分图

容斥 状态压缩

如果只有$t = 0$的边，那么容易想到$f(S, T)$表示左右点集的选择情况，直接跑一个状圧 DP。状态空间大小是$O(\sum_{i} \binom{n}{i}^2)$的（因为限定$|S| = |T|$）。不过很多状态是跑不到的，因为 DP 转移时我们会强制边的某个端点处在 lowbit 的位置。

对于$t = 1$的边，由于无法做类似 2-SAT 计数一样的东西，那么考虑容斥。如果我们直接把它拆成两条$t = 0$的边，那么可以发现原本的概率$\frac{1}{2}$变成了$\frac{1}{4}$。于是我们要补个$\frac{1}{4}$上去。方法是加入一条“边”连接了$a_1, b_1, a_2, b_2$，出现的概率是$\frac{1}{4}$。

对于$t = 2$的边同理，只不过概率是$-\frac{1}{4}$。

代码

守卫

区间 DP

（JXOI 2018）

本题思路容易受误导。实际上与凸包、单调栈等是没有关系的。

考虑区间$[l, r]$，我们必然会在$r$上放一个守卫。那么设这个守卫看到的位置依次是$p_1, \ldots, p_k$。分析一下$p$满足怎样的性质。

首先，$\dfrac{h_r - h_{p_i}}{r - p_i}$，即两点连线的斜率肯定是单调递增的。

其次，对于非空区间$[p_i + 1, p_{i + 1} - 1]$，只有$p_{i + 1}$可能看到其中的一些亭子。

简要证明：如果$p_j$（$j > i + 1$）能看到其中的一些亭子，那么$r$又能看到$p_j$和$p_{i+1}$，则$r$也能看到其中的数，矛盾。

换言之$[p_i + 1, p_{i + 1} - 1]$独立了。即我们划分出了一个子问题。

这样就可以区间 DP 了。设$f(i, j)$表示区间$[i, j]$的答案。

设$j$在$[i, j]$中能看见的下标最小的亭子是$k$。划分出最靠左的区间作为子问题，那么

$$f(i, j) = \min(f(i, k), f(i, k -1)) + f(k + 1, j)$$

可以理解为：在$k$或者$k - 1$上放一个守卫，取最小值。

时间复杂度$O(n^2)$。

代码