给定一个长度为\(n\)的\(01\)串\(s\)，用于表示一个环上的细胞的初始状态，其中第\(1\)个细胞与第\(2\)个、第\(n\)个细胞相邻；第\(n\)个细胞与第\(1\)个和第\(n-1\)个相邻。\(0\)表示细胞死亡，\(1\)表示细胞存活。接下来给定\(t\)轮操作，每一轮操作，根据上一轮细胞的状态更改此轮的状态。规则如下：
- 如果上一轮中与该细胞相邻的\(2\)个细胞中正好有\(1\)个存活，那么此轮中该细胞存活。否则此轮中该细胞死亡。
给定正整数\(t\)，请输出一个\(01\)串，表示\(t\)轮变化后每个细胞的存活状态。
数据范围：对于\(50\%\)的数据，保证\(3\le n\le 15\)，\(1\le T\le 10^{15}\)。
对于所有数据，保证\(3\le n\le 10^5\)，\(1\le T\le 10^{15}\)
样例：
Sample #1
Input
7 1
0000001
Output
1000010
Sample #2
Input
5 3
01011
Output
10100
50pts - 矩阵快速幂解法 - \(O(n^3\log t)\)
考虑用广义矩阵乘法代替普通矩阵乘法：把两数相乘改为两数取与，两数相加改为两数去异或。
则可以构建初始矩阵和递推矩阵（拿\(6\)阶举例，其他同理）：
\[A=\begin{bmatrix} 输入的01串\dots \end{bmatrix}, B=\begin{bmatrix} 0&1&0&0&0&1\\ 1&0&1&0&0&0\\ 0&1&0&1&0&0\\ 0&0&1&0&1&0\\ 0&0&0&1&0&1\\ 1&0&0&0&1&0 \end{bmatrix}\]点击查看代码
#include<bits/stdc++.h>
#define N 510
#define int long long
using namespace std;
int n,t;
string s;
struct Matrix{
int n,m;
bool a[N][N];
Matrix(int na,int ma){n=na,m=ma,memset(a,0,sizeof a);}
bool* operator [](int x){return a[x];}
Matrix(){memset(a,0,sizeof a);}
Matrix operator*(const Matrix &b) const{
Matrix res(n,b.m);
for(int i=1;i<=n;i++){
for(int j=1;j<=b.m;j++){
for(int k=1;k<=m;k++){
res[i][j]^=a[i][k]&b.a[k][j];
}
}
}
return res;
}
}a,base;
void qpow(int b){
while(b){
if(b&1) a=a*base;
base=base*base;
b>>=1;
}
}
signed main(){
cin>>n>>t>>s;
a.n=1,a.m=base.n=base.m=n;
for(int i=1;i<=n;i++) a[1][i]=s[i-1]-'0';
for(int i=1;i<=n;i++){
int p1=i-1,p2=i+1;
if(p1==0) p1+=n;
if(p2==n+1) p2-=n;
base[i][p1]=base[i][p2]=1;
}
qpow(t);
for(int i=1;i<=n;i++) cout<<a[1][i];
return 0;
}
但由于此方法复杂度是\(O(n^3\log T)\)，空间是\(O(n^2)\)，都无法承受。
100pts - 找规律&倍增 - \(O(n\log T)\)
假设现在有一个无限长的环：
...000000010000000...
进行变化（下面用#表示\(1\)，空格表示\(0\)），发现：
# //初始状态
# # //经过1次变化
# # //经过2次变化
# # # #
# # //经过4次变化
# # # #
# # # #
# # # # # # # #
# # //经过8次变化
# # # #
# # # #
# # # # # # # #
# # # #
# # # # # # # #
# # # # # # # #
# # # # # # # # # # # # # # # #
# # //经过16次变化
# # # #
# # # #
# # # # # # # #
# # # #
# # # # # # # #
# # # # # # # #
# # # # # # # # # # # # # # # #
# # # #
# # # # # # # #
.............
很神奇地，我们发现这是一个分形图（谢尔宾斯基三角形）。
当然这不是重点，我们发现，经过\(2^k\)次变化后，只有一开始的活细胞左边第\(2^k\)个细胞和右边第\(2^k\)个细胞是活的，其他全是死的。
因此我们可以得知任意一种环上，变化\(2^k\)次后每个活细胞向左右的贡献，即：对于每个活细胞，将其左&右边第\(2^k\)个细胞状态取反，自己也取反。
通过把\(t\)二进制分解，可以转化成若干个\(2^k\)次变化，重复上述操作即可。
时间复杂度\(O(n\log t)\)，可以通过。
注意是一个环，所以位置需要取模\(n\)。
#include<bits/stdc++.h>
#define N 100010
#define int long long
using namespace std;
int n,t,a[2][N];
string s;
int modn(int a){return ((a%n)+n)%n;}
signed main(){
cin>>n>>t>>s;
bool cur=0;
for(int i=0;i<n;i++) a[0][i]=s[i]-'0';
for(int ii=0,w=1;ii<55;ii++,w<<=1){//k=2^i
if(t&w){
cur^=1;
for(int i=0;i<n;i++) a[cur][i]=a[cur^1][i];
for(int i=0;i<n;i++) if(a[cur^1][i]) a[cur][i]^=1,a[cur][modn(i-w)]^=1,a[cur][modn(i+w)]^=1;
}
}
for(int i=0;i<n;i++) cout<<a[cur][i];
return 0;
}