0217测试
0217测试
T1
非公平组合游戏，先考虑简单的情况，不妨设 \(x_i\le a+b,a\le b\)。
那么一个 \(x_i\) 要么能被两个人各自拿一次，要么只能被 \(A\) 拿。
如果存在一个只能被 \(A\) 拿的 \(x\)，那么 \(A\) 必胜，他只需要一直拿两人都能拿的 \(x_i\)，让 \(B\) 拿不了，由于 \(A\) 最后多一个，所以必胜。
如果不存在只能被 \(A\) 拿的 \(x\)，胜负就与 \(x\) 的奇偶性和谁先手有关。但是此时两个人并不是等价的。如果有一个 \(x\) 满足 \(\max(2a,b)\le x\)，那么 \(A\) 只要拿掉它就能创造一个只能被 \(A\) 拿的，又变成必胜了，所以 \(B\) 会优先拿掉它们，但是如果由两个，\(B\) 就没办法。
分谁先手后手讨论，容易给出四种情况的充要条件，这些充要条件也是便于直接构造计算的。
考虑迁移到 \(x_i\) 无限制的情况，发现状态不会改变，如果先手必胜，那么先手按照模意义下的最优策略走，如果后手选择了能取模的，那么先手也选它取模，直到后手选择了一个不能取模的，此时可以平行对应到取模的情况，然后先手继续按照模意义下策略走。
后手必胜同理。
将整个转移图画出来，取模的情况就是完整转移图的低维投影。如果走了投影上没有的边，另一个人一定可以将点搬回投影上。
教训
犯错的原因是考虑简单情况时理所当然的认为 \(b\le y_i\) 时，该堆石子对 \(A,B\) 等价，实际上这不是等价的。
罗列证据时考虑要全面，或者干脆对拍一下。
T2
又没读题，最开始当成正回文做，手玩下样例保证理解对题。
在确定前半段的过程中，后半段也随之确定，建目标串的反串，对应点表示前半段出现什么时可以到该状态。然后跑 AC 自动机上动态规划，合并的时候由于一个串一定是由正串的一个前缀和反串的一个前缀拼起来的，如果可以拼起来那么当前 AC 自动机的节点一定满足它能代表其中较长那个前缀，直接暴力检查。
教训
- 手玩样例保证读对题。
- AC 自动机的点权值要弄对（除了 fa 之外还有 fail 的权值）。
- 要对拍。
T3
最开始考虑直接对树进行动态规划，设 \(dp[j][i]\) 表示有 \(i\) 个叶子，最大左儿子深度为 \(j\) 的方案总数。答案是一个前缀和，转移枚举左右儿子大小，也是前缀和形式，看上去不好优化。于是直接对前缀和动态规划，然后推出一个连分数形式的生成函数，不会了。
其实二叉树可以考虑转成序列做，由于一颗 \(n\) 个叶节点的满二叉树唯一对应一个 \(n-1\) 对括号的括号序列，要求等价于求 \(n-1\) 对括号，最深不超过 \(m-2\) 的括号序列个数。
可以抽象到二维平面上做，需要走到 \((n-1,n-1)\)，不能碰到 \(y=x+1\) 和 \(y=x-m+1\)。简记一条直线为它的截距，即 \(1\) 和 \(-m+1\)。
两种错误的方式
- 考虑先算碰到 \(1\) 的方案数，然后再算碰到了 \(-m + 1\) 但没碰到 \(1\) 的方案数。前者好算，后者对称后不能碰到 \(1\) 且不能碰到 \(1\) 关于 \(-m+1\) 的对称直线 \(-2m+1\)，递归解决该问题，边界为限制彻底放开。
- 考虑算碰到了 \(1\) 或者碰到 \(-m+1\) 的方案数，加上同时碰到的方案数，对于同时碰到的方案数，不容易一起算，考虑算先碰到 \(1\) 再碰到 \(-m+1\) 的方案数，同样考虑对称，先关于 \(1\) 再关于 \(-m+1\) 对称。同时要求走到 \(1\) 的过程中不能碰到 \(-2m+1\)，即减掉先碰到 \(-2m+1\) 关于 \(1\) 再碰到 \(1\) 的方案，递归解决。
容斥方式的本质
容斥本质上是通过对称构造了一个没有限制的问题，使得它和原问题不满足限制的情况一一对应。
这个对应的证明是基于对称问题中起点到终点一定穿过直线，因此将第一次碰到直线的前部分对称后一定可以对应到一种原问题的不合法情况，所以考虑原路径时，在对称路径第一次穿过直线后，原路径就不再是对称路径的对称路径了。所以第一种方式对直线 \(-2m+1\) 的限制是不合理的。
方式二看上去修了锅，实际上只是展开了一层手动修了，后面还是有一样的问题。
如果目标点在直线异侧，那么因为答案不是良定义的所以会错，需要特判为 \(0\)。
关于容斥方式，如果将括号序列视作一个 +1 -1 的序列，那么合法就是要求前缀和最小值不小于 \(0\)，我们将第一个小于 \(0\) 后的翻转，最后一定会到达 \(-2\)，因此不合法方案数等于到 \(-2\) 的无限制方案数。
一种正确的方式
全部方式减去要求碰到 \(1\) 或者 \(-m+1\) 的方式，发现先碰到 \(1\) 再碰到 \(-m+1\) 的方式被算重了。
然后要算先碰到 \(1\) 再碰到 \(-m+1\) 的方式，算这个的时候发现先到 \(-m+1\) 再到 \(1\) 再到 \(-m+1\) 的方式又被算重了，需要减去，如此递归下去做。
bonus
构造满二叉树的方式：
- 单个叶子节点是空串
- 有儿子的节点记左右儿子为 \(A,B\)，令它为
(A)B。 - 容易证明它们是一一对应的。
构造二叉树的方式：
空树是空串。
单节点的树是
()。有儿子节点的树记左右儿子的构造分别为 \(A,B\)，令它为
(A)B。容易证明方案是一一对应的。