题目:Kiki & Little Kiki 2
链接:http://acm.hdu.edu.cn/showproblem.php?pid=2276
分析:
1）如果前一盏灯亮着，则改变这一盏灯的状态。灯用0和1表示亮和不亮。
2）0和0=0，0和1=1，1和0=1，1和1=0；这是异或，或者说 (左边的状态+原来的状态)%2=现在的状态，或者表示为(左边的状态+原来的状态)&1=现在的状态。
3）构造矩阵，快速幂优化。$T = \left[ \begin{array}{cccccc} 1 & 1 & 0 & ... & 0 & 0 \\ 0 & 1& 1 & ... & 0 & 0 \\ 0 & 0 & 1 & ... & 0 & 0\\ ... & ... & ... & ... & ... & ... \\ 0 & 0 & 0 & ... & 1 & 1 \\ 1 & 0 & 0 & ... & 0 & 1 \end{array} \right] $
由于状态只有0和1，所以在矩阵乘法中，$ (C[i][j]+=A[i][k]*B[k][j])%=2 $可改写为 $ C[i][j]$ ^= $ A[i][k] $ & $B[k][j] $
#include <bits/stdc++.h> using namespace std; typedef long long LL; int MOD; struct Matrix{ int n,a[101][101]; Matrix(int _n,int f=0):n(_n){ memset(a,0,sizeof a); if(f==1)for(int i=0;i<n;++i)a[i][i]=1; } }; Matrix operator*(Matrix& A,Matrix& B){ Matrix C(A.n); for(int k=0;k<C.n;++k) for(int i=0;i<C.n;++i)if(A.a[i][k]) for(int j=0;j<C.n;++j) C.a[i][j]^=A.a[i][k]&B.a[k][j]; return C; } Matrix operator^(Matrix A,int n){ Matrix Rt(A.n,1); for(;n;n>>=1){ if(n&1)Rt=Rt*A; A=A*A; } return Rt; } int main(){ char s[105]; for(int n,m;~scanf("%d",&m);){ scanf("%s",s);n=strlen(s); Matrix F(n,1); F.a[n-1][0]=1; for(int i=1;i<n;++i)F.a[i-1][i]=1; F=F^m; for(int i=0,t;i<n;++i){ t=0; for(int j=0;j<n;++j) t^=(s[j]-48)&F.a[j][i]; putchar(char(t+48)); } puts(""); } return 0; }
原文：https://www.cnblogs.com/hjj1871984569/p/9979468.html