A
一条蛇，有 \(K(K\le 6)\) 个格子，格子必须连续且不能重叠。
在 \(n\times m(n,m\le 3000)\) 的矩阵中放置，有一些格子是不能放的，问方案数。
B
一棵树 \((n\le 50000)\).
每次询问 \([l1,r1],[l2,r2]\) 在 \(rt\) 为根下两两 lca 的异或和。
先处理以 \(rt\) 为根的问题，发现 \(lca_{rt}(u,v)=lca_1(u,rt)\otimes lca_1(v,rt) \otimes lca_1(u,v)\).
这是因为三者之间总有两个相同，消掉即可。
我们突然想到一道题：P4211 [LNOI2014] LCA
我们考虑把 \(1\sim n\) 分块，设块长为 \(s\)。
对于第 \(i\) 块，我们预处理出 \(f_{i,j}\) 表示第 \(i\) 个块中所有点和 \(j\) 的 lca 的异或和。
这是可以换根 dp 实现的。复杂度 \(O(n^2/s)\)
至于询问 \([l1,r1],[l2,r2]\)，我们可以先拆询问成为前缀的形式，变成了查询 \([1,l]\times [1,r]\) 中两两 lca.
标签：rt,le,r2,格子,23,异或,lca,2023.8,模拟 From： https://www.cnblogs.com/Simon-Gao/p/17652758.html