HDU2276——Kiki & Little Kiki 2

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2276

题目意思：给予一个01字符串，表示一串灯的明亮状态，现在每过一秒，如何这个灯的左边的灯是亮的，我们就改变他的明亮状态。（从左往右依次更新）注：第一个的左边是最后一个（即0的左边是n-1），问n秒后所有灯的明亮状态。

思路：采用矩阵快速幂啊！这个题十分有意思，采用了位运算，是真的没有想到。

以上是以样例一(0101111)为例的系数矩阵,我们发现对于相邻的两位只存在四种情况00,01,10,11，其中00,01保持原样不变，10和11分别变成11和10，我们惊奇的发现(1&1)^(1&1)=0，(1&1)^(1&0)=1，是不是满足这个变换？而(0&1)^(0&1)=0，(0&1)^(1&1)=1保持不变。这个就是这道题的难点，希望可以记住这个类型的变换。这样我们就可以通过上面的系数矩阵通过矩阵快速幂快速得到n秒后的状态了！！！

代码：

//Author: xiaowuga

#include <bits/stdc++.h>

#define maxx INT_MAX

#define minn INT_MIN

#define inf 0x3f3f3f3f

#define maxn 101

using namespace std;

typedef long long ll;

int n;

struct Matrix{

    ll mat[maxn][maxn];

    Matrix operator * (const Matrix & m) const{

        Matrix tmp;

        for(int i=;i<n;i++)

            for(int j=;j<n;j++){

                tmp.mat[i][j]=;

                for(int k=;k<n;k++){

                    tmp.mat[i][j]^=mat[i][k]&m.mat[k][j];

                }

            }

        return tmp;

    }

};

Matrix POW(Matrix &m,ll k){

    Matrix ans;

    memset(ans.mat,,sizeof(ans.mat));

    for(int i=;i<n;i++) ans.mat[i][i]=;

    while(k){

        if(k&) ans=ans*m;

        k/=;

        m=m*m;

    }

    return ans;

}

int main() {

    ios::sync_with_stdio(false);cin.tie();

    ll num;

    while(cin>>num){

        string q;

        cin>>q;

        n=q.size();

        Matrix m,f;

        memset(m.mat,,sizeof(m.mat));

        memset(f.mat,,sizeof(f.mat));

        for(int i=;i<n;i++) f.mat[i][]=q[i]-'';

        m.mat[][]=m.mat[][n-]=;

        for(int i=;i<n;i++) m.mat[i][i-]=m.mat[i][i]=;

        Matrix x=POW(m,num);

        Matrix ans=x*f;

        for(int i=;i<n;i++) cout<<ans.mat[i][];

        cout<<endl;

    }

    return ;

}

巴特西

HDU2276——Kiki & Little Kiki 2

最新文章

热门文章