2023.8.23 模拟赛
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 异或和.
考虑先把 \([1,l]\) 拆成若干整块，和剩下的散块。
对于这里的若干整块，我们计算这些整块跟 \([1,r]\) 的贡献。是已经被预处理的，前缀和即可。
剩下的散块，要跟 \([1,r]\) 贡献，考虑把 \([1,r]\) 也拆成若干整块和散块，整块的贡献是预处理的。
剩下两个散块，直接暴力配对即可。
至于换 \(rt\) 为根的贡献，也是容易的。
复杂度 \(O(s^2+n/s)\).
综合起来，取 \(s=n^{1/3}\) 是最优的，总共是 \(O(n^{5/3})\) 的级别。
注意要卡常数，可以把遍历整块换成前缀和减少常数，也可以把多次换根 dp 合起来一次搞定。
C
\(n\) 个数，\(q\) 次询问 \([L,R]\) 内有多少区间满足 \(\gcd\) 为 \(d\).
\(a_i\le 10^6,n,q\le 10^5\)。
首先知道 \(a_i\) 往（前）后求 \(\gcd\) 值的连续段个数是 \(\log a_i\) 级别的。
于是我们可以预处理出这些连续段。
使用莫队，维护一个桶，对于加一个数，减一个数，只需要枚举以其为开头的区间的 \(\gcd\) 的值，在桶中贡献即可。