自动搬运

查看原文

来自洛谷，原作者为

	Snakes **

搬运于2025-08-24 21:54:20，当前版本为作者最后更新于2018-04-10 19:08:39，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

算法一

我会随机！

由于我忘了设置多组数据，期望得分$0$至$100$。

算法二

我会模拟！

复杂度$O(t^2)$，期望得分$60$。

但是很多人忘记题目给出的是环形……

算法三

我会正解！

实际上是数学题，显然时刻$t$第$k$盏灯的状态为

$$\left(\sum_{i=0}^t C_t^ia_{(k+i-1) \bmod n+1}\right) \bmod 2 $$

求和即可。复杂度$O(t)$，期望得分$100$。

给证明？

实际上，这道题是这个问题的子问题。

亮灯问题

有$n$盏灯环形排列，顺时针依次标号为$0..n-1$。初始时刻为$0$，所有灯的亮灭（我们称之为状态）随机。下一时刻每盏灯的亮灭取决于当前时刻这盏灯与顺时针方向下一盏灯的亮灭。若两盏灯状态相同，则下一时刻该灯灭，否则该灯亮。
　　试求：当$n$满足什么条件时，能保证在初始状态随机的情况下，时刻$n$所有灯均为灭？

答案

$$n=2^p \quad (p \in \mathbb{N})$$

证明

环形排列下，直接对灯的标号进行加减可能会出现越界的情况，所以我们需要对结果取模，即第$i$盏灯顺时针方向下$k$盏灯为第$(i+k) \bmod n$盏灯。

定义$S_t^i$表示时刻$t$第$i$盏灯的亮灭，$0$表示灭，$1$表示亮。

异或？

异或运算应用于逻辑运算（也可以看作为二进制下）。$\oplus$为异或运算符。其运算法则相当于不带进位的二进制加法：

$$\begin{aligned}0 \oplus 0=0\\ 1 \oplus 0=1\\ 0 \oplus 1=1\\ 1 \oplus 1=0\end{aligned} $$

即二进制位相同则结果为$0$，不同为$1$。

根据异或运算的定义及题意，我们可以得到：

$$S_t^i=S_{t-1}^i \oplus S_{t-1}^{(i+1)\bmod n}$$

又因为异或运算等价于不带进位的加法，而我们只关注$S_t^i$的奇偶，所以有：

$$S_t^i=\left(S_{t-1}^i+S_{t-1}^{(i+1)\bmod n}\right) \bmod 2 $$

由于在时刻$t$，标号为$i$的灯受到上一时刻标号$i$、$(i+1) \bmod n$的灯的影响，而在时刻$(t-1)$，标号$(i+1) \bmod n$灯受到时刻$(t-2)$下标号$(i+1) \bmod n$、$(i+2) \bmod n$灯的影响。继续推导可知，时刻$t$下$i$灯受到时刻$0$下$i$灯到$(i+t) \bmod n$灯初始状态的影响，并且可能不止一次。

注意有$a \bmod p+b \bmod p=(a+b) \bmod p$的性质，所以方便起见，我们可以将取模运算放在最后操作。以下$S$的值域将会扩充到自然数集，但是其意义仍为$S \bmod 2$。

受几次影响？

定义$Z_t^k$表示时刻$t$下标号为$i$的灯受到$(i+k) \bmod n$灯初始状态的影响次数，则有：

$$S_t^i=\sum_{j=0}^t Z_t^j S_0^{(i+j) \bmod n}$$

根据$S$与$Z$的定义，我们有：

$$S_{t+1}^i=\sum_{j=0}^{t+1} Z_{t+1}^j S_0^{(i+j) \bmod n}=S_t^i+S_t^{i+1} $$

展开上式，得：

$$\sum_{j=0}^{t+1} Z_{t+1}^j S_0^{(i+j) \bmod n}=\sum_{k=0}^t Z_t^k S_0^{(i+k) \bmod n}+\sum_{l=0}^t Z_t^l S_0^{(i+l+1) \bmod n} $$

因为$Z$的定义，所以$Z_t^{-1}$与$Z_t^{t+1}$是无意义的，值为$0$，则上式可改写成下式形式：

$$\begin{aligned}\sum_{j=0}^{t+1} Z_{t+1}^j S_0^{(i+j) \bmod n}&=\sum_{k=0}^{t+1} Z_t^k S_0^{(i+k) \bmod n}+\sum_{l=0}^{t+1} Z_t^{l-1} S_0^{(i+l) \bmod n}\\ &=\sum_{k=0}^{t+1} \left(Z_t^k S_0^{(i+k) \bmod n}+Z_t^{k-1} S_0^{(i+k) \bmod n}\right)\\ &=\sum_{k=0}^{t+1} \left(Z_t^k+Z_t^{k-1}\right) S_0^{(i+k) \bmod n} \end{aligned} $$

所以有$Z$的推导公式：

$$Z_{t+1}^k=Z_t^{k-1}+Z_t^k$$

根据定义可以得到边界条件：

$$Z_0^0=1$$

不难发现$Z$与$C$的边界条件与推导公式相同，则有：

$$Z_t^k=C_t^k$$ $$S_t^i=\left(\sum_{j=0}^t C_t^j S_0^{(i+j) \bmod n}\right) \bmod 2 $$

均灭？

若时刻$n$所有灯均灭，则上一时刻即时刻$(n-1)$时，标号$i$的灯应受所有灯影响或不受任何一灯影响。但通过$C_{n-1}^k$的奇偶性我们发现，不受任何一灯影响是不可能的。则$i$灯应受所有灯影响，即为：

$$C_{n-1}^k=1 \quad (n \in Result, k \in \mathbb{N}, 0 \leq k \leq n-1) $$

不妨将$C_t^k \bmod 2$（即杨辉三角对$2$取模的图形）列出来。不难发现规律：第$2^p-1$行符合全为$1$的条件，也就是说，答案为$n=2^p (p \in \mathbb{N})$（别忘了$n=1$的情况！）而如果我们将$1$染为黑色等边三角形，将$0$染为白色等边三角形（如图），我们将得到Sierpinski三角形（谢尔宾斯基三角形）。Sierpinski三角形是分形图形的一个经典图形，在Matrix67的博客里也有提及。

Sierpinski三角形？

接下来，我们需要证明为什么第$2^p-1$行符合全为$1$的条件。则我们需要证明：

$$C_{2^p-1}^k \equiv 1 \pmod 2 \quad (k \in \mathbb{N}, 0 \leq k \leq 2^p-1) $$

展开得：

$$\frac{(2^p-1)!}{k!(2^p-1-k)!} \equiv 1 \pmod 2$$

定义$G_i$表示$i$分解质因数后$2$的个数。定义$T_r^l=\sum_{j=l}^r G_j$，则上式可由下式证得：

$$T_k^1=T_{2^p-1}^{2^p-k}$$

若将$i$写为二进制，则$G_i$为二进制下$i$末尾$0$的个数。不难发现有以下两条性质：

$$G_i=G_{i+2^j} \quad (i, j \in \mathbb{Z^{+}}, 2^j \gt i) $$$$G_{2^j}=j \quad (j \in \mathbb{Z^{+}})$$

二进制下$(i+2^j)$可由二进制下$i$的第$j$位由$0$变$1$得到，由于第$j$位在限制条件下一定比$i$的最高位更高，所以在第$j$位添加$1$对末尾$0$的个数即$G$无影响，第一条式子得证。第二条式子也可以根据$G$的定义得到。

接下来我们需要证明：在$1..2^p-1$的范围内，$G$以$2^{p-1}$为轴对称。

首先注意到，在$p=1$的条件下，该结论成立。我们需要将结论扩展到$p \in \mathbb{Z^{+}}$。

若在$1..2^p-1$范围内，$G$以$2^{p-1}$为轴对称，则有：

$$G_i=G_{2^{p-1}+(2^{p-1}-i)}=G_{2^p-i}$$

又因为$G_i=G_{i+2^p}$，所以：

$$G_{i+2^p}=G_i=G_{2^p-i}$$

并且有$G_{2^p}=G_{2^p}$，所以在$1..2^{p+1}-1$范围内，$G$以$2^p$为轴对称。所以我们可以将$p=1$下的结论扩展到$p \in \mathbb{Z^{+}}$。

根据$G$的对称性，我们有下式成立：

$$T_k^1=T_{2^p-1}^{2^p-k}$$

所以下式成立：

$$\frac{(2^p-1)!}{k!(2^p-1-k)!} \equiv 1 \pmod 2$$

得：

$$C_{2^p-1}^k \equiv 1 \pmod 2 \quad (k \in \mathbb{N}, 0 \leq k \leq 2^p-1) $$

得证。

根据第$2^p-1$行均为$1$，我们可以推得第$2^p$行只有$C_{2^p}^0$与$C_{2^p}^{2^p}$为$1$，其余为$0$，这两个$1$将分别向下扩展到$2^{p+1}-1$行，形成与$1$到$2^p-1$行相同的Sierpinski三角形。

所以杨辉三角在对$2$取模的情况下，将会形成Sierpinski三角形。

我们的问题也证明完毕，证得答案为$n=2^p (p \in \mathbb{N})$。

所以细心的你看完这篇文章一定会证明啦～

实际上，我们用到的是受影响次数的计算式，将其代入题目就能得到题解给出的式子啦！