题解 P3937 【Changing】
Snakes
·
·
题解
算法一
我会随机！
由于我忘了设置多组数据，期望得分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})。
所以细心的你看完这篇文章一定会证明啦～
实际上，我们用到的是受影响次数的计算式，将其代入题目就能得到题解给出的式子啦！