矩阵快速幂优化与运算次数无关的迭代计算

这一题看起来像是枚举，但是 n 的范围是1e9，即使能够想到用动态规划来做，时间复杂度还是不能够接受 的，每次叠塞子的时候只与上一次在顶上的塞子的点数以及我们设置的规则有关，而与我们是第几次摇塞子无关，所以我们可以用矩阵快速幂要优化

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int mo = (int)1e9 + 7;
const int N = 7;
int n, m;
int op[] = { 0,4,5,6,1,2,3 };

// 矩阵快速幂的模版
struct matrix {
	int c[N][N];
	matrix() {
		memset(c, 0, sizeof c);
	}
	friend matrix operator*(matrix a, matrix b) {
		matrix z;
		for (int i = 1; i <= 6; i++) {
			for (int j = 1; j <= 6; j++) {
				for (int k = 1; k <= 6; k++) {
					z.c[i][j] = (z.c[i][j] + a.c[i][k] * b.c[k][j])%mo;
				}
			}
		}
		return z;
	}
};

matrix quickpow(matrix x, int y) {
	// x 是我们的迭代矩阵, y 是次数
	matrix ans;
	for (int i = 1; i <= 6; i++) ans.c[i][i] = 1;
	while (y) {
		if (y & 1) ans = ans * x;
		x = x * x;
		y >>= 1;
	}
	return ans;
}

signed main() {
	cin >> n >> m;
	if (n == 0) {
		cout << 0; return 0;
	}
	map<pair<int,int>, int> mp;
	for (int i = 1; i <= m; i++) {
		int a, b;
		cin >> a >> b;
		mp[{a,op[b]}] = 1;
		mp[{b, op[a]}] = 1;
	}
	matrix x; // 设置我们的转移矩阵
	for (int i = 1; i <= 6; i++) {
		for (int j = 1; j <= 6; j++) {
			if (mp[{i, j}]) x.c[i][j] = 0;
			else x.c[i][j] = 4;
			//cout << x.c[i][j] << " ";
		}
		//cout << endl;
	}
	matrix ans;
	// 我们需要特判断一下
	for (int i = 1; i <= 6; i++) ans.c[1][i] = 4;// 第一次的答案
	ans = ans * quickpow(x, n - 1);
	int last = 0;
	for (int i = 1; i <= 6; i++) {
		last = (last + ans.c[1][i]) % mo;
	}
	cout << last;
	return 0;
}

其实我还是不怎么懂转移矩阵怎么来的