洛谷翻译：https://www.luogu.com.cn/problem/AT3951
诡异DP……
当 A A A和 B B B变成 2 A − B 2A-B 2A−B的时候，就让 A A A当 B B B的父亲。最终会形成一棵带儿子相对顺序的树。
一个点的贡献可以视作 2 d i c i x i 2^{d_i}c_ix_i 2dicixi的形式，其中 x i x_i xi太大，所以直接将其当成未知数考虑。
d i d_i di表示节点的深度。 c i c_i ci为正负号。
接下来考虑怎么求出 c i c_i ci：按深度优先顺序加点，加点前将父亲的子树中所有点的 c i c_i ci取反。
这样子考虑太麻烦，不如换种方式考虑：按照深度优先顺序计算，对于某个点 x x x，看 y y y是 x x x的从右往左数第几个儿子，如果是 x x x的第偶数个儿子，则 c y c_y cy取 − c x -c_x −cx，否则取 c x c_x cx。
搞完之后，对于每个点，统计它的儿子的个数，如果为奇数则取反。
我们要计算不同的方案数，只需要保证存在 d i d_i di或 c i c_i ci不同。
DP解决。首先 d i d_i di用按层转移的方式来搞定。按层转移的时候，已经确定了前面这些层最终的 c i c_i ci，这样最后一层有奇数个儿子的点数是可以记录的（奇数个儿子可以修正 c i c_i ci）。
f i , j f_{i,j} fi,j表示已经放了 i i i个节点，最后一层有 j j j个节点的儿子的个数为奇数，此时的方案数。
转移考虑当前这层“长出”了一些节点。
为了方便计算将 c i c_i ci差分，如果和父亲相同记作 1 1 1否则记作 − 1 -1 −1。接下来只关心下一层的点有多少个和父亲相同，多少个和父亲不同。
（正确性？。。。。。。）
如果一个点有 k k k个儿子，那么其中 ⌊ k 2 ⌋ \lfloor \frac{k}{2} \rfloor ⌊2k⌋个儿子的 c i c_i ci和它不同（先忽略儿子的儿子对儿子颜色的影响）。
现在设下一层长出了 k k k个节点，有 k − j 2 \frac{k-j}{2} 2k−j个点是和父亲不同的。（注意不是整除）
设经过儿子的儿子调整之后，真正的和父亲不同的个数有 x x x个。于是有 ∣ x − k − j 2 ∣ |x-\frac{k-j}{2}| ∣x−2k−j∣个节点的 c i c_i ci需要修正，即这就是下一层儿子个数为奇数的节点数。
注意这里只转移到 ∣ x − k − j 2 ∣ |x-\frac{k-j}{2}| ∣x−2k−j∣。虽然变成 ∣ x − k − j 2 ∣ + 2 z , z ∈ N |x-\frac{k-j}{2}|+2z,z\in N ∣x−2k−j∣+2z,z∈N也是合法的，但是这样就会同时存在“不同”修正为“相同”和“相同”修正为“不同”，这时候就会出现算重的情况。
时间复杂度就是 O ( n 4 ) O(n^4) O(n4)的了。
