A
目前见过的最阴间的A。
寻找规律，发现最后的回文串一定是由若干个周期拼起来的。当周期长度为偶数时，\(S\) 和 \(S'\) 可以各拿半个周期。
于是 kmp 求出 border，再判一下，但是我不会理性证明这个结论。
然后官方题解给出的做法是这样的：
- \(S'\)的开头 \(N\) 项和末尾 \(N\) 项都是 \(rev(S)\)，所以如果 \(K<2N%\)，\(S'\) 是确定的，可以直接判断。
- 当 \(K>2n\) ,那么 \(S'=rev(S)+T+rev(S)\)，因为 \(S+S',S'+S\)回文，那么 \(S+rev(S)+T+rev(S),rev(S)+T+rev(S)+S\) 回文，\(rev(S)\) 和 \(S\) 抵消，得出 \(rev(S)+T\) 和 \(T+rev(S)\) 是回文。然后此时 \(T\) 的长度为 \(K-2N\)，变为了完全相同的子问题。所以最开始将 \(K%=2N\)即可。
B
发现 \(\big||x-a|-b\big|=\min(|x-(a-b)|,|x-(a+b)|)\)，那么将 $a_i 土 b_i $ 作为关键点 \(c_j\) \(f_T(x)=\min |x-c_j|\)，即 \(x\) 与最近关键点的距离。
然后用 \(set\) 维护关键点，区间查询就找到区间最近的关键点即可。
C
发现操作可逆，考虑化标判断。
从简单的情况入手：如果没有偶数，那么不能动；如果只有一个偶数，那么这个偶数可以移动到任意位置，然后使用这个偶数，可以交换相邻两个奇数，于是可以完成对奇数的排序。
于是我们考虑尽量让这个序列变得有序：将奇数放前面，偶数放后面，然后奇偶分别排序。
要达成这一目的，考虑以下性质：
- 如果没有偶数或所有奇数之间的距离都大于2，那么所有奇数都不能动。否则一定可以将所有奇数放在前面，偶数放在后面：对于一对距离小于2的奇数，与它们相邻的偶数都可以被放到它们之前/之后，于是这堆奇数可以在偶数中移动，最后可以把所有奇数 “粘” 在一起，放到开头。
- 只要有偶数，就可以把一段奇数排序；如果一段偶数个数大于2，就可以将它们排序。
所以如果这个序列有偶数且存在一对距离不大于2的奇数，那么可以把奇数放前面，排序；偶数放后面，如果个数大于2，排序。
否则奇数不能动，把所有偶数个数大于2的段排序。
综上，就可以把序列化标，然后判断一下 \(A\) 和 \(B\) 化标是否得出同样的结果即可。
D
如果将题目改成：要求每次操作必须将 \(G\) 变小，那么可以直接 dp。\(f_i=1/0\) 表示 \(G=i\) 时先手/后手获胜。然后考虑转移，\(i\) 局面的后续局面 \(j\)，必定满足 \(j\ |\ i\) ，于是枚举约数，但是现在要判断是否存在 \(gcd(a_k,i)=j\)。于是考虑容斥，令 \(g_j=\sum_{k=1}^n gcd(a_k,i)=j,g'_j=\sum_{k=1}^n j\ |\ gcd(a_k,i)\)，而由于 \(j\ |\ i\)，\(g'_j=\sum j\ |\ a_k\)，与 \(i\) 无关，然后容斥算出 \(g_j\)。如果 \(g_j>0\)，\(i\) 就可以从 \(j\) 转移。
但是原题并没有要求将 \(G\) 变小，可以在黑板上选出一个 \(G\) 的倍数，拖时间。如果当前 \(i\) 的后续局面只有 \(1\)，那么先后手都会拖时间，然后胜负就只与剩余的 \(i\) 的倍数个数的奇偶性有关，而游戏操作到 \(i\) 的过程，以前操作的一定都是 \(i\) 的倍数，于是我们记下状态 \(f_{i,0/1}\)，表示到 \(i\) 的时候已经进行了偶数/奇数次操作的胜负。然后再考虑会不会在其他情况下拖时间，讨论一下可以发现，如果当前所有的后继状态，奇数/偶数都没有后手必胜，那么在这里，谁先有效操作谁输，于是开始拖时间，对于这样的状态，\(f_i\) 就只与 \(a\) 中有多少 \(i\) 的倍数的奇偶性有关 。
总复杂度 \(O(nlog^2n)\)。
E
看到异或，从线性基的角度考虑。如果 \(S\) 包含 \(0\)，不放令 \(0\) 分到 \(T1\) 中，那么\(T1 \subseteq f(T1)\)，且线性基不变。但是我们可以在 \(T2\) 上进行操作，如果只将所有包含某个基底的数都放入 \(T2\)，那么这个基底在 \(T2\) 中就会被消去，线性基的大小恰好变小 1。可以发现一次确实不能消掉多个基底，所以如果 \(S\) 包含 \(0\)，那么答案就是线性基的大小。
对于 \(S\) 不包含 \(0\) 的情况，发现如果在最开始将每个数都异或上一个相同的值，那么一次操作之后的结果不会改变（每两个数异或的时候被抵消了），而进行了一次操作以后 \(S\) 必定包含 \(0\)。所以我们只需要在开始时每一个数都异或上第一个数，第一个数就变成了 \(0\)，再求出线性基大小即为答案。
F
很离谱的计数题。
首先可以发现，对于每个无向树，我们从叶子开始分配方向，至多只有一种分配方案满足 \(D\) 的条件。于是，满足条件的无向树就和每个点出度分别为 \(D_i\) 的有向树一一对应（注意，是有向树，不是内向/外向树）。
直接算有向树比较抽象，于是我们给树指定一个根，再将每个点的出边编号。而原来的一颗无根有向树就对应了 \(n * \prod D_i\) 棵“有根有向边有编号”树。
然后我们来计算这样的树的数量。由于有了根，那么每一条边的方向就要么是父亲指向儿子（向下），要么是儿子指向父亲（向上）。我们分开计算这两种边的方案。
于是计算过程可以分为一下三步：
- 枚举一个点集 \(S\)，规定只有 \(S\) 中的点和父亲之间的边是向上的，且对于 \(S\) 中的每个点，选出其向上的这条边的编号，方案数为 \(\prod_{i\in s} D_i\)。
- 计算给这些向上的边确定每条边的终点的方案数。
- 计算向下的边每条边确定终点的方案数。
令 \(m= |S|\)。
第三步是最好做的，由于每一条边都有了编号，那么我们按编号顺序一条一条确定终点。因为是向下的边，所以终点必须还没有父亲，又因为不能有环，终点不能是起点的祖先。第二步以后还剩下 \(n-m\) 个弱连通块，所以第一条边的终点有 \(n-m-1\) 种选择（每个弱连通块只有一个没有祖先的点，还不能选和起点一个若联通块的那个）。以此类推，第 \(i\) 条边有 \(n-m-i\) 种选择，所以第三步一共有 \((n-m-1)!\) 种方案。
再看第二步，第二步执行之后的结果是 \(n\) 个点，\(m\) 条边的内向树森林，森林不好算，我们添加一个“超级根” 0，让所有没父亲的点连一条边指向 0。那么现在就是要算以 0 为根，且 0 的入度为 n-m 的内向树有多少棵。有根内向树的方案显然和无根无向树的方案一一对应，所以用 prufer 序来计算。指定 prufer 序每一项是最大标号叶子的父亲，则 0 一定会成为最后留下来两个点之一，在 prufer 序中 0 就一定会出现 n-m-1 次，所以 prufer 序的方案数是 \(C_{n-1}^{n-m-1}*n^m\)，但是这样算出来的结果包含了指定 \(S\) 集合的方案，但这是第一步算的内容，所以我们要除掉 \(C_n^m\)，最后得到第二步的结果为 \(n^{m-1}*(n-m)\)。
于是，最后的答案可以写为ii，最后一个非00元素在位置j
\[\sum_{m=0}^n (n-m-1)!*n^{m-1}*(n-m)*\sum_{|S|=m} \prod _{i\in S} D_i \]然后对于 \(\sum_{|S|=m} \prod _{i\in S} D_i\)，可以直接使用背包计算，复杂度 \(O(n^2)\)。使用分治NTT，就可复杂度 \(O(nlog^2n)\)。
但是注意到这道题满足 \(\sum D_i =n-1\)，我们可以先把相同的 \(D_i\) 一起用二项式定理算出来，然后按 \(D_i\) 从大到小乘起来。\(D>=i\) 的至多有 \(n/i\) 项，所以总复杂度不超过 \(\sum \frac ni log \frac n i\) ，据说是 \(O(nlogn)\)。
标签：那么,155,奇数,题解,sum,rev,偶数,ARC,可以 From： https://www.cnblogs.com/william555/p/17083213.html