题目:Kiki & Little Kiki 2

链接:

分析:

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 
     
      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
      
       >=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