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

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

当前运算用矩阵表示即

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';
}