NOI25F类游记

· · 个人记录

个人记录，非题解

D1T1

好像随便做了一下就过了。

D2T2

考虑 a_i=0 就等价于不能操作了。

操作只能构成一些从左到右和从右到左的链。

相当于一些区间被缩到了某个位置，这个位置的值可以计算。

发现如果确定了某些位置有值后，如果排除掉每个极短的奇偶和相等区间则存在从左到右确定每个区间的唯一确定方法。

## D1T3 注意到答案都是 $2$ 的幂次。 考虑特殊性质，相当于左右 DFS 序相反，和相同等价。 确定左根后可以递归确定右根，然后反复横跳。 到一个集合相同的点对时可以重新确定左右。 所以答案只和子树异或和的等价类数量有关。 ## D2T1 可以只通过观察极短的 ``101`` 和 ``110`` 子串确定。 ## D2T2 先枚举 $\&$ 和，然后分别对两个集合容斥。 然后相当于一些数可以给第一个集合，一些数可以给第二个集合。 都可以给的贡献是 $2a+1$，可以给一个的贡献是 $a+1$。 然后对于第二次容斥的结果算第一次的容斥系数和，发现恰好是 $2^{\text{popcount}}$。 所以只要做 FWT，注意到存在 $a_i=0$ 导致不能逆元，可以去掉 $0$ 后通过 $0$ 的数量让 FWT 只转移适合的部分。 ## D2T3 考虑每个位置可以执行一次技能或者不执行技能。 将是否执行技能作为变量，用每种卡的个数对变量做约束 然后这些约束应该 trivial polylog。