AGC050C

观察操作形式，设 \((a,b)\) 表示对手两侧（可以交换顺序）还剩下多少格子可以走，初始状态 \((+\infty ,+\infty)\)

玩家的操作是让对手的状态由 \((a,b)\) 变成 \((\min(a,b),0)\)

那么你手上的操作多于 \(\log\) 次那么一定可以让对方死掉，因为每次操作必然让最开始的 \(a+b\) 减少 \(\frac1 2\)

那么设 \(dp_{i,j}\) 表示操作完成了 \([i,n]\)，你还需要 \(j\) 操作才能让对方输（或者对方还有 \(2^j\) 个格子能走） 的方案数

转移考虑如果这个操作可以不由对方执行，那么转移给 \(dp_{i-2^j-1,j+1}\) 因为对手需要走这么多步来达到当前的 \(dp_{i,j}\)

而这里需要注意的是这个转移要满足前面 \(2^j\) 个中没有玩家的必操作步

而如果这个操作可以由对手进行的话直接当作废步转移给 \(dp_{i-1,j}\)，因为有用的步都在上面转移了，对手剩余的回合最好选择呆在区间中点一动不动

ARC087F

考察这个限制：发现对于一条边而言，使其经过最多次数一定是让 \((i,p_i)\) 尽量处于边的两侧，贡献是 \(\min(siz_u,n-siz_u)\)

回到全局角度最大化该式子的和值就是找到重心，\((i,p_i)\) 分别处于重心的两个不同子树之中

然而直接统计排列很困难所以考虑减去不合法方案数，设 \(dp_i\) 表示钦定 \(i\) 个位置的 \(p_i\) 和自己是一个子树里面的

对于某个子树的 \(dp_i=\binom {siz}i^2 i!\)，这里前面是选择 \(i\) 和 \(p_i\) 的方案，后面因为这些 \(p_i\) 可以乱放所以要乘阶乘

枚举重心的所有子树进行背包即可完成统计

每个 \(dp_i\) 在完成钦定之后剩下的位置可以随便放 \(p_i\)，要乘 \((n-i)!\)，最后附加上 \((-1)^i\) 作为容斥系数即可

博主学了三四年OI并不理解基础容斥式子，下简记

考察有 \(k\) 个错误位置的排列在答案中的计算次数，它会在每个 \(dp_i\times (n-i)!\) 中计算 \(\binom ki\) 次

再不会容斥基础组合恒等式还是会的，所以就正确了

AGC052B

考虑该操作的本质：如果以 \(1\) 为根进行 \(\rm{DFS}\)，将根到某点路径上的每个边的异或和作为该点的权值，那么对于和根不相连的点，操作一条边可以视作点权交换

设 \(a_x\) 表示用 \(w_1\) 作为边权的时候的点权，\(b_x\) 表示用 \(w_2\) 作边权的时候的点权

但是这样的思路明显有限制：和根相连的边在操作的时候并不能用点权交换的方法表示

那么建立一个虚根和 \(1\) 相连，如果能找到一个根和 \(1\) 连边的边权 \(W\) 满足 \(a_x\oplus W=b_y\) 且 \(x,y\) 两两配对那么满足条件

由于 \(n\) 是奇数，将所有的上述对应式子异或起来之后发现 \(W=\rm{xor}_ {i=1}^n x_i\oplus y_i\)

得到 \(W\) 之后判断是不是 \(\{a_i\oplus W\}\) 和 \(\{b_i\}\) 相等即可