学了算法提高课-矩阵快速幂后的奇思妙想
我们知道两个二进制数据异或即为两个数相加取余,我们可以将矩阵表示出来
当前运算用矩阵表示即
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';
}