雅礼集训 2017 day8 价：注意。
CF1129D Isolation
考虑令 (f_i) 表示前 (i) 个位置划分为若干段的合法方案数。
考虑转移，(f_i) 可以被 (f_j) 转移当且仅当 ((j,i]) 满足题目要求。考虑维护 (f_j) 。现在需要转移 (f_i) ，意味着新加入了一个 (a_i) ，考虑这个 (a_i) 对原序列的改变有哪些。首先令上一次出现 (a_i) 的位置为 (p') ，上上次为 (p'') ，那么有：
- 对于 (jin(p',i]) ：(a_i) 的出现次数为 (1) ，((j,i]) 的"出现恰好一次的元素个数"值为 ((j,i-1]) 的值加一。
- 对于 (jin(p'',p']) ：(a_i) 的出现次数为 (2) ，((j,i]) 的"出现恰好一次的元素个数"值为 ((j,i-1]) 的值减一。
- 对于 (jleq p'') ：没有影响。
这样的话考虑 序列分块 维护 (f_j) 。每一块以"出现恰好一次的元素个数"为下标开个桶，随时记录答案即可快速转移了。
CF724E Goods transportation
考虑 最大流，原点向 (i) 连 (s_i) ，(i) 向汇点连 (p_i) ，(i<j) 连 (c) 。
边数 (O(n ^2)) 级别不可接受，考虑到因为 最大流 等价于 最小割，解决原图最小割。
因为边都是从小点往大点连，考虑令 (f_{i,j}) 表示前 (i) 个点 (j) 个选择与 (s) 相连的最小代价。转移的时候只需要考虑当前点是与 (s) 连还是与 (t) 连即可，需要割掉的边的贡献可以很好的算出来。
CF691E Xor-sequences
矩阵乘法优化 DP 即可。
？感觉这个 CF 题单不行，还是做别人的杂题记录好了。
「雅礼集训 2018 Day4」Magic
考虑设 (f_{i}) 表示恰好有 (k) 个相邻位置相同的方案数，(g_i) 表示钦定有 (k) 个位置相同，剩下随意的方案数。考虑 (g) 怎么求，然后就可以反演出 (f) 。
这是个卷积的形式，分治 NTT 即可。
*「雅礼集训 2017 Day8」价
根据 hall 定理，对于减肥药的集合 (s) ，与其有边相连的药材集合 (N(s)) 一定满足 (|s|leq |N(s)|) 。
将 源点 往 减肥药 连 INF + p 边，减肥药 向 药材 连 INF+ 边，药材 连 汇点，边权 INF。因为最小割割的肯定是左边的边或者右边的边，并且需要至少割掉 (n) 条，又因为边权为 INF，所以最优一定是恰好割掉 (n) 条。
这样子的话就相当于 不选的减肥药个数+选的药材个数 为 (n) ，同时因为 选的减肥药个数+不选的减肥药个数 为 (n) ，因此 选的减肥药个数=选的药材个数，满足题目要求。
这样子的话只需要最小割即可。
感觉这题挺迷幻的，我在想的时候一直在想怎么处理 减肥药个数 和 药材个数 相等的限制，结果最后得此巧妙解决。（虽然我感觉 INF 边可是可以用来调度，但是直接连 INF 证明恰好割 (n) 条太迷幻了。
「雅礼集训 2017 Day11」PATH
考虑差分一下，对于原坐标 ((x_0,x_1,cdots,x_{n-1})) 将其重新定义为 ((x_0-x_1,x_1-x_2,cdots,x_{n-2}-x_{n-1},x_{n-1})) ，将这个叫做"新坐标"。容易发现对于一个新坐标对应了一个唯一的原坐标，且不同新坐标对应的原坐标一定不同起点的新坐标显然是 ((0,0,cdots,0)) ，终点的新坐标也很好确定。
对于这种游走方式，对于新坐标来讲，就是将某一位加一，（如果有前一位的话）再将前一位减一，且保证任意时刻没有某一维坐标小于 (0) 。
不难发现操作策略为：往第一位叠上一个 (1) ，或者通过若干次操作将第一位上的一个 (1) 送到后面的某个位。而这个"送到后面的某位"经过了若干步，它们在操作序列中可以随意排列，对 (1) 来说，我们只需要在意一个"送到后面的某位"操作序列的开头位置。
那么现在这个问题就成功降维了，只需要对"叠 (1) / 送到后面的某位"序列计数即可（剩下的计数是十分简单的）。那么这就是一个二维的经典问题了。
这个做法口胡，待实现。
听说和 杨表 有关的有一种做法，待补。