日记

传奇耐骗王。

T1 # Link to T1

把 $a$ 异或上 $b$，再把 $a$ 按照异或差分。（就是说 $\bigoplus_{j = 1}^{i}a'_j = a_i$）这样一个区间 $[l,r]$ 翻转就变成了取反 $a'_l,a'_{r + 1}$。我们把 $l \longleftrightarrow r + 1$ 建边。那样就分成了许多连通块。每个连通块之间的情况数是独立的。

对于每个连通块单独考虑。我们掏一个生成树出来，那么我们一定只用翻转树边就行了。对于每种生成树，方案都是固定的。于是一个连通块的方案数就是这个连通块的生成树数量。为 $2^\text{非树边数量}$。

如何构造答案呢？我们从叶子开始。dfs 时记录一个 $pre$ 表示从哪条边走到的 $u$。因为我们是从叶子往上生成方案的，所以翻转 $[l_{pre},r_{pre}]$ 不影响下面的点。于是直接判断 $a'_u$ 是否为 $1$，是就翻转 $a'_u$ 和 $u$ 的 $fa$，并构造答案。

T2 # Link to T2

我们发现，每个 $b_{i,j}$ 会对 $n + m - 1$ 个数造成贡献。也就是说 $b$ 数组的总和 $tot$ 是 $a$ 数组的总和 $sum$ 的 $\frac{1}{n - m + 1}$。这样我们就能求出 $tot$。

接下来我们考虑如何求 $b$ 第 $i$ 行的和 $totr_i$。我们发现，如果把 $a$ 的第 $i$ 行的数加起来，就相当于把 $b$ 的第 $i$ 行算了 $m$ 次，再把 $b$ 除了第 $i$ 行的加起来。也就是说：

解出来发现 $totr_i = \frac{tot - sumr_i}{m - 1}$。如法炮制求出 $totc_j$。又有 $a_{i,j} = totr_i + totc_j - b_{i,j}$，就可以解出 $b_{i,j}$ 了。

T3 # Link to T3

赛时都想得到，这里就不说了。

码力该比思维好练吧？

一个 manacher 卡我一晚上。

T4 # Link to T4

神秘小随机化。明天再问问随机化大佬。

后日谈 # Link to 后日谈

原来 NOIp 只有 $272$ 也可以进队啊？