AcWing
  • 首页
  • 活动
  • 题库
  • 竞赛
  • 商店
  • 应用
  • 文章
    • 题解
    • 分享
    • 问答
  • 吐槽
  • 登录/注册

AcWing 1960. 闪烁    原题链接    简单

作者: 作者的头像   imnoob ,  2022-01-15 19:37:03 ,  所有人可见 ,  阅读 71


5


学了算法提高课-矩阵快速幂后的奇思妙想

我们知道两个二进制数据异或即为两个数相加取余,我们可以将矩阵表示出来

当前运算用矩阵表示即
矩阵表示

res 矩阵即为单位矩阵,让运算矩阵进行快速幂
单位矩阵

结果矩阵需要输入便不再提供图片

算法复杂度为$O(logB)$
与找环结果相比
结果对比

下面那个19ms的为找环算法
可见,矩阵快速幂几乎无法被卡

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int n;
long long b;

void mutli(int ans[][16], int a[][16], int b[][16]){
    int temp[16][16] = {0};
    for(int i = 0;i < n;i ++)
        for(int j = 0;j < n;j ++)
            for(int k = 0;k < n;k ++)
                temp[i][j] = (temp[i][j] + a[i][k] * b[k][j]) % 2;
    memcpy(ans, temp, sizeof temp);
}

int main()
{
    cin >> n >> b;
    int f[16][16] = {0}, r[16][16] = {0}, res[16][16] = {0};

    for(int i = 0;i < n;i ++)
        cin >> f[i][0];
    for (int i = 1; i < n; ++i)
        r[i][i - 1] = r[i][i] = 1;
    r[0][n - 1] = r[0][0] = 1;
    for(int i = 0;i < n;i ++)
        res[i][i] = 1;
        //init matrix

    while(b){
        if(b & 1) mutli(res,res,r);
        mutli(r,r,r);
        b >>= 1;
    }
    //fast pow
    mutli(f, res, f);
    for(int i = 0;i < n;i ++)
        cout << f[i][0] << '\n';
}

0 评论

你确定删除吗?
1024
x

© 2018-2022 AcWing 版权所有  |  京ICP备17053197号-1
用户协议  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息