[Solution] P7783 「MCOI-Zero / AC6-M14」Gracemeria Patrol

hy233 · 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{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}，上式等价于：

若 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} 需要的操作次数，反之即为