自动搬运

查看原文

来自洛谷，原作者为

	hy233 每天摆烂的菜狗

搬运于2025-08-24 22:33:03，当前版本为作者最后更新于2024-04-28 20:29:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

如果确定了第一行的操作，那么其他行的操作也确定了。因为若操作了前 $i$ 行，第 $i+1$ 行的位置能操作当且仅当其正上方为 $1$。

我们不妨用广义矩阵刻画这一转移：设 $\boldsymbol{a_i}$ 为第 $i$ 行的数所构成的向量，$\boldsymbol{f_i}$ 为修改完前 $i$ 行之后第 $i$ 行构成的向量。令 $\boldsymbol A=\begin{bmatrix} 1 & 1 & 0 & 0 & \cdots \\ 1 & 1 & 1 & 0 & \cdots \\ 0 & 1 & 1 & 1 & \cdots \\ \vdots & \vdots & \vdots & \vdots & \ddots \\ \end{bmatrix}$，则 $\boldsymbol{f_i=f_{i-1}A\oplus a_i}$。其中 $\oplus$ 为异或。

所以 $\boldsymbol{f_n=((f_1A\oplus a_2)A\oplus a_3\cdots)A\oplus a_n}$，第 $n$ 行没有下一行给他消了，所以 $\boldsymbol{f_n=0}$。化简把 $\boldsymbol{f_1}$ 提出可得：

$$\boldsymbol{f_1A^{n-1}=\sum_{i=2}^na_iA^{n-i}}$$

右边显然可以预处理，如果 $\boldsymbol{A^{-1}}$ 存在那么移到右边去就结束了。打表发现 $\boldsymbol{A^{-1}}$ 不存在当且仅当 $m \equiv 2 \pmod 3$。

Proof：考虑方程 $\boldsymbol{xA=v}$：

$$\boldsymbol{\exist x_1\ne x_2,x_1A=x_2A=v\Leftrightarrow (x_1-x_2)A=0\Leftrightarrow \exist u\ne 0,uA=0 } $$

如果存在 $\boldsymbol{uA=0}$，那么 $\boldsymbol{f_1}$ 就有多个解，不符合条件。尝试构造这样的 $\boldsymbol{u}$，上式等价于：

$$\left\{\begin{matrix} u_1\oplus u_2=0 \\ u_1\oplus u_2\oplus u_3=0 \\ \cdots\\ u_{m-2}\oplus u_{m-1}\oplus u_m=0\\ u_{m-1}\oplus u_m=0 \end{matrix}\right.$$

若 $u_1=u_2=0$，则$\boldsymbol{u=0}$。

否则 $u_1=u_2=1$，$\boldsymbol{u}=(1,1,0,1,1,0,\cdots)$，当且仅当 $m \equiv 2 \pmod 3$ 时满足 $u_{m-1}\oplus u_m=0$。

所以当 $m \equiv 2 \pmod 3$ 时 $\boldsymbol{xA=v}$ 有多解，反之则有唯一解。 归纳可以得到 $\forall k,\boldsymbol{xA^k=v}$ 有着同样的性质。

所以区间询问时，当 $m \equiv 2 \pmod 3$ 时我们输出 $-1$，否则直接解出 $\boldsymbol{f_l=(\sum_{i=l+1}^ra_iA^{r-i})A^{-(r-l)}}$。验证一下 $\boldsymbol{a_l}$ 是否可以唯一得到 $\boldsymbol{f_l}$ 即可。$k=l$ 时，答案为 $\boldsymbol{a_l\rightarrow f_l}$ 需要的操作次数，反之即为 $\boldsymbol{f_{k-1}}$ 中 $1$ 的个数。

关于数值计算，预处理 $\boldsymbol{A^k},k\in [-n,n]$，$\boldsymbol{\sum_{i=l+1}^ra_iA^{r-i}}$ 类似的东西可以差分计算。注意到 $m\le 50$，用 ull 压一下可以去掉一个 $m$ ，复杂度 $O(nm^2+qm)$。