P2203 Blink 题解

· · 题解

传送门

好像并没有矩阵快速幂的题解，那我来写一篇

题目分析

对于每两盏灯，只考虑右灯变化，分为四种情况：

左灯为 1，右灯为 1，右灯变为 0；

左灯为 0，右灯为 0，右灯不变，为 0；

左灯为 1，右灯为 0，右灯变为 1；

左灯为 0，右灯为 1，右灯不变，为 1；

设第 i 盏灯状态为 s[i]。

不难发现：

s[i] = s[i-1] \oplus s[i]

可以构造如下 N\times N 递推矩阵，用于进行递推：

1 & 1 & 0 & \cdots & 0 & 0 & 0\\ 0 & 1 & 1 & \cdots & 0 & 0 & 0\\ 0 & 0 & 1 & \cdots & 0 & 0 & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots &\\ 0 & 0 & 0 & \cdots & 1 & 1 & 0\\ 0 & 0 & 0 & \cdots & 0 & 1 & 1\\ 1 & 0 & 0 & \cdots & 0 & 0 & 1\\ \end{bmatrix}

（灯环形排列，需要头尾相接）

举个例子，当 N=5 时，矩阵即为：

1 & 1 & 0 & 0 & 0\\ 0 & 1 & 1 & 0 & 0\\ 0 & 0 & 1 & 1 & 0\\ 0 & 0 & 0 & 1 & 1\\ 1 & 0 & 0 & 0 & 1\\ \end{bmatrix}

递推矩阵推出来后，直接矩阵快速幂即可。

朴实无华的代码

#include<bits/stdc++.h>
using namespace std;
#define int long long//十年OI一场空，不开long long见祖宗
inline int read(){int x=0;char ch=getchar();while(ch<'0'||ch>'9')ch=getchar();while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}return x;}
const int N=20;
const int p=2;
int n,m;
int s[N];
struct MS
{
    int c[N][N];
    int n,m;
};
MS operator *(const MS &a,const MS &b)//矩阵乘法
{
    MS c;
    c.n=a.n;
    c.m=b.m;
    for(int i=1;i<=a.n;i++)
        for(int j=1;j<=b.m;j++)
            c.c[i][j]=0;
    for(int i=1;i<=a.n;i++)
        for(int j=1;j<=b.m;j++)
            for(int k=1;k<=a.m;k++)
                c.c[i][j]=(c.c[i][j]+a.c[i][k]*b.c[k][j]%p)%p;
    return c;
}
MS fpow(MS a,int k)//矩阵快速幂
{
    MS e;
    e.n=n;
    e.m=m;
    for(int i=1;i<=n;i++) e.c[i][1]=s[n-i+1];
    while(k>0)
    {
        if(k&1) e=a*e;
        a=a*a;
        k>>=1;
    }
    return e;
}
MS init()//递推矩阵构造
{
    MS a;
    a.n=n;
    a.m=n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            a.c[i][j]=0;
    for(int i=1;i<=n;i++)
    {
        a.c[i][i]=1;
        a.c[i][i+1]=1;
    }
    a.c[n][1]=1;//头尾相接
    return a;
}
MS a;
signed main()
{
    int k;
    m=1;
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<=n;i++) s[i]=read();
    a=init();
    MS ans=fpow(a,k);
    for(int i=n;i>=1;i--)
    printf("%lld\n",ans.c[i][1]);
    return 0;
}