方知蓦然回首之时
那人却已不在灯火阑珊处

考虑最暴力的做法,列出 n 个生成函数,FWT 到一起,复杂度 \mathcal O(n \times 2^k \times k) ,显然不能通过。

考虑三元组 (a_i, b_i, c_i)ans_k 的贡献,等价于三元组 (0, a_i \operatorname{xor} b_i, a_i \operatorname{xor} c_i)ans_{k \operatorname{xor} a_i} 的贡献。考虑这样将题意转化后,生成函数只有 0a_i \operatorname{xor} b_ia_i \operatorname{xor} c_i 下标上有值(分别为 a, b, c)。那么经过一次 FWT 后,只有四种值,分别为 a+b+c, a+b-c, a-b+c, a-b-c

考虑将 n 个生成函数加起来做 FWT ,假设 a+b+c, a+b-c, a-b+c, a-b-c 分别在其中出现了 x, y, z, w 次,那么这个位置在正常做法情况下的值应该为 (a+b+c)^x \times (a+b-c)^y \times (a-b+c)^z \times (a-b-c)^w ,也就是说我们需要解出这个 x, y, z, w 的值。

首先显然的 x + y + z + w = pp 是这位上当前的值。需要注意的是,这个 a, b, c 并不一定需要是题目中给出的,所以我们可以分别取 (0, 1, 0)(0, 0, 1) ,列出两个方程,此时我们若再通过改变 (a, b, c) 来列方程,则可以通过两个已有的来表示,本质相同的,需要考虑别的方式得到新的方程。

考虑构造一个新的多项式,对于每个 k = b_i \operatorname{xor} c_ik \text{+=} 1 ,这样的话可以得到一个新的方程 x + y + z + w = qq 是这位上当前的值。

这样的话我们就得到了四个本质不同方程,可以解除上面的 x, y, z, w ,得出正常 FWT 后应该得到的点值,再将其 IFWT 一次即可得到答案。

READ MORE

DP 。用 f_{u, 0} 表示 u 点被染黑的概率,f_{u, 1} 表示 u 点被染白,但是其祖先中有点被染黑的概率,用 f_{u, 2} 表示 u 点被染白,且其祖先没有被染黑的点的概率。所求答案即 \displaystyle{\sum_{i=1}^n f_{i, 0}}

READ MORE

考虑一段数 a_{l..r} 是公差为 k 的等差数列,当且仅当:

  • \max a_{l..r} - \min a_{l..r} = k(r - l)

  • \gcd abs(a_i - a_{i-1}) = k, (i \in (l, r])

  • \max pre_{l..r} < lpre_i 表示 a_i 上一次出现的位置。

线段树维护一下即可。

READ MORE

榕树还是当年的榕树,你却不是当年的你了……

先点名表扬下这个题面,写的也太优美了吧 QAQ ...

假设我们只需要判断 1 号点能否成为最后的答案,用 f_i 表示取完 i 所在的子树的所有点后榕树的心离 i 的最近距离,那么答案即求 [f_1 = 0].

考虑 f_u 怎么求,最难消去的孩子是 \max (siz_v) (v \in son_u) 的孩子 v ,可以用其他子树的 siz 来填补这棵子树。代码中,另一部分的大小表示为 half ,这一部分表示为 f[max]

对于不以 1 为根的情况,可以把根节点到当前点 u 的路径缩成一个点来考虑,可以上下 DP 。

READ MORE