题目：P12925 [POI 2022/2023 R2] 病毒 / Wirus

题目大意

对于一个二进制序列，其每次变化为：将所有二进制全部左移一位，将从左到右第一位与第二位异或，并将其变为最后一位，删去第一位。求该序列 $d$ 次变化后的结果。

题目分析

我们看这道题，我们把异或换成加法运算。我们发现，他让我们维护有一个固定变化规律的序列，再一看 $d$ 范围，就大概知道这道题的时间复杂度不是 $O(\sqrt{n})$ 就是 $O(\log{n})$。

先考虑时间复杂度较大的，好像没有什么思路。那么考虑 $O(\log{n})$ 时间复杂度。在这个时间复杂度的无非就二分，快速幂那么几个。于是，我们就可以很自然的想到一个在这个时间复杂度上，还可以维护一个序列规则变化的东西 —— 矩阵快速幂。

实现分析

变换为加法我们非常熟悉，无非就是让原先序列作为一个列向量与一个矩阵做矩阵乘法：

$\begin{bmatrix}0&1&0&\cdots&0&0\\0&0&1&\cdots&0&0\\0&0&0&\cdots&0&0\\\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\0&0&0&\cdots&0&1\\1&1&0&\cdots&0&0\end{bmatrix} \ast \begin{bmatrix}a_1\\a_2\\a_3\\\vdots\\a_{n-1}\\a_n\end{bmatrix}= \begin{bmatrix}a_2\\a_3\\a_4\\\vdots\\a_{n}\\a_1 + a_2\end{bmatrix}$

变换 $n$ 次的式子无非就是

$(\begin{bmatrix}0&1&0&\cdots&0&0\\0&0&1&\cdots&0&0\\0&0&0&\cdots&0&0\\\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\0&0&0&\cdots&0&1\\1&1&0&\cdots&0&0\end{bmatrix})^n \ast \begin{bmatrix}a_1\\a_2\\a_3\\\vdots\\a_{n-1}\\a_n\end{bmatrix}$

异或的计算性质与加法基本一致，也就是说矩阵的定义是完全可以兼容异或的，于是我们可以爆改原本的矩阵运算，获得一个异或版本的矩阵运算，同理的我们可以得到以下这些东西

变化一次的式子

$\begin{bmatrix}0&1&0&\cdots&0&0\\0&0&1&\cdots&0&0\\0&0&0&\cdots&0&0\\\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\0&0&0&\cdots&0&1\\1&1&0&\cdots&0&0\end{bmatrix} \ast \begin{bmatrix}a_1\\a_2\\a_3\\\vdots\\a_{n-1}\\a_n\end{bmatrix} = \begin{bmatrix}a_2\\a_3\\a_4\\\vdots\\a_{n}\\a_1 \bigoplus a_2\end{bmatrix}$

进一步的，变换 $n$ 次的式子

$(\begin{bmatrix}0&1&0&\cdots&0&0\\0&0&1&\cdots&0&0\\0&0&0&\cdots&0&0\\\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\0&0&0&\cdots&0&1\\1&1&0&\cdots&0&0\end{bmatrix})^n \ast \begin{bmatrix}a_1\\a_2\\a_3\\\vdots\\a_{n-1}\\a_n\end{bmatrix}$

代码实现

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n , m;
using D=vector<bitset<1005> >;//合理的使用此类方法可以有效的让代码更简洁
D a(1005);
void init(int n)//初始化矩阵
{
	for(int i = 1 ; i < n ; i++)a[i][i + 1] = 1;
	a[n][1] = a[n][2] = 1;
}
D mul(D b , D c)//考虑实际需要，在这里只实现两个行列相同的矩阵的乘法
{
	D ans(1005);
	for(int i = 1 ; i <= n ; i++)
	{
		for(int k = 1 ; k <= n ; k++)
		{
			if(b[i][k])ans[i] ^= c[k];
		}
	}
	return ans;
}
D fpow(D b , int k)//b表示传入矩阵，k表示次数
{
	D c(n + 5);
	for(int i = 1 ; i <= n ; i++)c[i][i] = 1;//初始化出一个单位矩阵，好比普通快速幂将初值定义为1
	while(k)
	{
		if(k & 1)c = mul(c , b);//可以证明，对于非0的k其最高位总是为1的
		b = mul(b , b);
		k >>= 1;
	}
	return c;
}

signed main()
{
	cin.tie(0) , cout.tie(0);
	ios::sync_with_stdio(0);
	cin>>n>>m;
	init(n);
	a = fpow(a , m);
	char s;
	bitset<1005>ans , e;
	ans &= 0;
	for(int i = 1 ; i <= n ; i++)
	{
		cin>>s;
		if(s == '1')e[i] = 1;
	}//e数组表示输入的列向量
	for(int i = 1 ; i <= n ; i++)
	{
		for(int k = 1 ; k <= n ; k++)
		{
			if(a[i][k])ans[i] = ans[i] ^ e[k];
		}
	}//不同行列的矩阵乘法仅使用一次，故在此单独实现
	for(int i = 1 ; i <= n ; i++)cout<<ans[i];
	return 0;
}