NOI2023训练赛12
门把手集合
每个点的价值是子树中与自身距离不超过 \(k\) 的点权两两异或的平方和。
异或想到拆位，平方只与两个为有关，枚举两个位置，合并子节点权值，实时删去距离大于 \(k\) 的节点，可以做到 \(O(n\log^2 V)\)。
本题卡空间，dsu on tree 做到时间复杂度 \(O(n\log n\log^2 V)\)。
武装直升机
dp 转移是取 \(f\) 和极差的 max，区间极差随右端点增大而减小，有效 \(f\) 值则增大，dp 转移点有单调性，可以单调队列维护区间 \(\text{min,max}\) 和 \(f\)，时间复杂度 \(O(n)\)。
NOI2023训练赛13
线下单杀
四字名称
把胜负场数看做 \(x,y\) 坐标：
\[a_{x,y}=\frac{\binom x {x+y}}{2^{x+y}}a_{0}{0}
\]
答案合法要求对于任意 \(a_{x,y} (x\in[0,n-1],y\in[0,m-1])\) 是 \(2\) 的倍数。
由 kummer 定理可得，\(\binom x {x+y}\) 的 \(p\) 次幂数是 \(\sum_{i=1}^\infty \lfloor\frac{x+y}{p^i}\rfloor-\lfloor\frac{x}{p^i}\rfloor-\lfloor\frac{y}{p^i}\rfloor\)
所以只取右上角 \(30\times 30\) 个点计算即可。
事实上数据只要取 \(20\times 20\) 个点就行了。