总结

集合

考虑枚举子集和，统计有多少个子集的和为当前枚举的子集和，然后我们记个结论：\(x^y=x^{y \mod (p - 1)}\)，然后就过了

P3488

一眼二分图（网络流启动），但是考虑到图很大，所以我们考虑直接判断是否是二分图，考虑一个区间，如果总数比这个区间所能承载的人都要大，那么肯定会寄，所以用线段树维护每个区间的最大字段和

连通块

考虑没有限制，那么就是一个树上的 \(dp\)，加上限制后，我们考虑，每加一个子树相当于加一个dfn序，所以我们可以记录当前dfn最后一个位置，那么如果要加一个子树，那么就可以从限制点的位置-1的地方转移过来，但是我们只要处理限制点，所以我们可以离散化，然后只处理限制点

跳棋

考虑整个序列是如何变动的，我们观察到，当两个 1 组在一起时，是可以一直动的，因为碰到一个 1 时，可以从跳跃换成接替，那么我们便可以将 11 压在一起变成 2，那么数组终将会有四种元素：\(0,1,2,?\)

考虑没有问号的情况，那么整个问题变成了 2 的放置，我们发现 1 没有贡献，所以我们只用看 0 和 2 的个数，那么变成了在 0 和 2 的个数和中选取 2 的个数个位置放置 2，那么我们可以用 \(dp\) 的方式来给 \(?\) 分配符号，考虑到答案是与 0 的个数， 和 2 的个数有关，所以我们记录下 0 的个数和 2 的个数，那么我们初始认为状态时 \(f_{ijk}\) 表示前 \(i\) 个，有 \(j\) 个 2 \(k\) 个 0

但是我们要思考 \(j\) 和 \(k\) 要如何统计，那么统计我们需要知道上一位是什么，但是考虑到 \(2\) 的统计是当前面有偶数个 \(1\) 的时候才能凑齐 2，所以我们要加一个前面有奇数偶数个 1 所以状态变成 \(f_{ijk0/10/1}\)

考虑转移，那么从当前是什么来考虑，分几种当前是什么的情况，然后注意当只有当前面有偶数个 1 的时候才能统计 \(2\) 的个数

最后对于目标状态，由于已经不存在 ? 所以可以直接用组合数做，然后要滚动数组

总结

由于思路错误，导致大部分时间在想 Dinic 如何解决删人问题，所以其它题没有想（不过我Dinic写对了！）。