https://vjudge.net/contest/615530
A
首先破环为链。
直接算比较麻烦，考虑拆贡献，考虑一个区间作为一个联通块的贡献。
首先我们需要求出一个区间中连边的方案数，发现其实之和区间长度还有这个区间内部有多少点之间有连边有关。
显然我们有递推式 \(f_i = (i-1)f_{i-2}\) 既枚举第 \(i\) 个位置和哪个位置匹配。
然后考虑算出 \(g_{l,r}\) 表示 \([l,r]\) 作为一个合法极大联通块的方案数。
直接算同样不好算，因为可能会算重，所以考虑容斥。
既 \(g_{l,r} = f_{l, r} – \sum_{i=l}^{r-1}{g_{l,i} f_{i + 1,r}}\)。
然后对答案的贡献就是 \(g_{l,r} \times f_{r + 1, l + n – 1}\)。
B
首先考虑一个更弱化的问题，给定一个字符串，如何判定其是否能够转化成一个字符。
遇到这种题要考虑寻找不变量，人类智慧的，我们设 \(A = 1, B = 2\)，则我们发现经过一次操作之后 \(sum \bmod 3\) 不变。
但是这并不充分，因为显然 \(112\) 可以弄成 \(1\) 但是 \(121\) 不行，所以另一个条件是要有相邻相同的数，加上这个条件之后就构成了充要条件，充分性证明可以考虑归纳。
然后我们再考虑一个进阶的问题，对于一个字符串能否判定其是否可以转化成另一个字符串。
首先特判掉没有任意两个相邻相同的情况。
我们发现我们可以贪心地匹配每一个字符。
我们有如果能转化那么一定能够贪心匹配上并且最后剩下一段 \(sum \bmod 0\) 的段。
必要性显然，充分性可以考虑因为最后一段会和谁匹配上，一样可以证明。
于是 dp 就很显然了，我们倒着 dp，每次转移最近一段的合法段，然后最后答案就是 \(f_n\)。
C
先分析题目性质。
子序列性质很好，当我们删去一个数时显然前缀相同，而我们只需比较后缀，如果当前 \(a_{i} \not = a_{i+1}\)，那么显然有 \(a_i > a_{i+1}\)，如果 \(i=len\) 那么也无所谓。
但是如果 \(a_i = a_{i+1}\)，那么条件可能就会变得复杂，但是我们可以钦定我们一定删一个连续段的最后一个数字，因为无论删去哪个结果一定相同。
但是还是很棘手，我们可以考虑这样子想，如果我们依靠 \(x\) 删掉了 \(y\)，那么我们就把 \(y\) 连向 \(x\)。
显然最后形成了一个广义的笛卡尔树。
于是我们可以考虑笛卡尔树 dp，因为是广义的，我们可以枚举第一个最小值出现的位置，设 \(f_{i,j}\) 表示有 \(i\) 个点，值域为 \([j,V]\) 时的方案数。
转移有 \(f_{i,j} = \sum_{k=1}^i{f_{k-1,j+1}f_{i-k,j} \sum_{t=i-k+1}^i {\binom{t-1}{i-k}}}\)。
D
\(x\) 关于 \(y\) 对称后的结果为 \(2y-x\)。
同样考虑被删除的点挂在他的删除原因上。
由于 \(2^n < 10^100\)，所以显然结果不同当且仅当每个数系数至少有一个不同。
那么在这颗树上显然你的深度就是系数前 \(2\) 的次数。
我们考虑按层填点，那么我们就只需要考虑符号的限制了。
分析一下最简单的情况。
一个点接了两个儿子和三个儿子。
+ -
- + + - +
发现如果一个点有奇数个儿子，那么会有一个取反的操作，同时一个点有 \(\frac{son}{2}\) 个奇数儿子。
但是我们发现在这之后我们对一个点父亲的操作还是会改变该点的正负性，不过这不重要，因为我们只要有两种不同颜色就好了，我们并不关心他们到底是什么颜色的，我们可以钦定其父亲全部为 \(+\) 号。
于是设 \(f_{i,j}\) 表示已经填了 \(i\) 个点，且上一层要改变 \(j\) 个点有奇数个儿子，且我们钦定所有特殊点颜色相同。
那么我们枚举我们这层钦定要有 \(x\) 个 \(+\)，\(y\) 个 \(-\)。
当然你可能发现了一点问题，上一层每个点的正负号不一定相同，我们的钦定有可能是错误的。
但是仔细分析之后我们发现其实只有那 \(j\) 个特殊点比较有问题，因为其他不管怎么样一定都是有一半的异色点。
但是我们可以钦定这 \(j\) 个特殊点一定颜色相同，不然我们显然可以选择两个异色特殊点，然后将他们都变得不再特殊，产生的贡献是一样的。
钦定特殊点颜色相同是这题的核心思想。
那么实际上我们除了放了 \(j\) 个 \(+\) 之外还有 \(x+y-j\) 个点，平分为 \(\frac{x+y-j}{2}\) 个点，所以如果这层是叶子的话那么一共有 \(\frac{x+y+j}{2}\) 个 \(+\)，所以我们就要修改 \(\lvert x – \frac{x+y+j}{2} \rvert\) 个点。
然后就做完了。
E
改天再写。
F
考虑转化成括号序列计数问题。
我们将红色视为 \((\)，蓝色视为 \()\)。
先考虑跑一遍括号匹配，假设最后剩下 \())(((\)，有 \(x\) 个 \()\)，\(y\) 个 \((\)。
那么有 \(t=\frac{k-x-y}{2}\) 个括号匹配了。
显然我们可以先使得 \(t\) 个人合法。
然后考虑剩下的括号要怎么分配，显然 \()\) 全给一个人一定最优，那么其实合法的条件就是 \(n-t+x \le y\)。
然后考虑对上面那种情况计数。
括号序列计数肯定考虑转化成格路计数。
就是每次走 \((+1,+1)\) 或者 \((+1,-1)\)，要走到 \((k,y-x)\) 的方案数且要触碰到 \(y=-x\) 这条线但是不能跨过他。
考虑经过一条直线的方案数是好计算的，就是对称之后到达的方案数，那么我们直接用 \(y=-x\) 的方案数减去 \(y=-x-1\) 的方案数就得到我们要的答案了。
然后我们发现这个式子只和 \(x+y\) 有关，而 \(x+y\) 正好就是 \(n-2 \times t\)，那么我们直接枚举 \(t\) 就做完了。
G
H
可以转化成格路计数。
就是网格图上经过的红线个数，发现一定能经过 \(max(n,m)\) 条，然后再加上 \(x=y\) 时的特殊 \(\frac{1}{2}\) 的贡献就好了。
I
J
改天再写
K
L
M
N
O
可能算一个 trick 题？
第一个转化，转化操作。
相等限制比较不好处理，我们考虑对每个位置异或上 \(i \bmod 2\)，这样我们就变成了交换不同的两个数。
而我们显然不会交换相同的数，这就使得题目变得清晰了起来。
然后再考虑交换次数，而这也有结论就是前缀和只差的绝对值之和。
然后再考虑加入 \(?\) 的贡献，可以想到拆贡献，然后就做完了。
