这题布吉岛为啥可以降幂

P为质数， 所以对次方降幂， 取模(mod - 1)

设f[i][j][k]， i表示摆到第几个位置， j中0表示A的个数为偶数， 1为奇数， k中0表示B的个数为偶数， 1为奇数。

推出递推方程， 就可以矩阵快速幂了！
f[i][0][0] = 2 * f[i - 1][0][0] + f[i - 1][0][1] + f[i - 1][1][0];
f[i][0][1] = 2 * f[i - 1][0][1] + f[i - 1][1][1] + f[i - 1][0][0];
f[i][1][0] = 2 * f[i - 1][1][0] + f[i - 1][1][1] + f[i - 1][0][0];
f[i][1][1] = 2 * f[i - 1][1][1] + f[i - 1][0][1] + f[i - 1][1][0];
系数矩阵为
2 1 1 0
1 2 0 1
1 0 2 1
0 1 1 2 
#include <bits/stdc++.h>
using namespace std;
#define sz(a) ((int)(a).size())
typedef long long ll;
#define me(a, b) (memset(a, b, sizeof a))
const ll INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
 
struct M{
	ll m[5][5];
	M()
	{
		me(m, 0);
	}
};
M mul(M a, M b)
{
	M res;
	for (int i = 0; i < 4; i++)
		for (int j = 0; j < 4; j++)
			for (int k = 0; k < 4; k++)
				res.m[i][j] = (res.m[i][j] + a.m[i][k] * b.m[k][j]) % mod;
	return res;
}
void fpow(ll n)
{
	M a;
	for (int i = 0; i < 4; i++)
		a.m[i][i] = 1;
	M b;
	b.m[0][0] = 2, b.m[0][1] = 1, b.m[0][2] = 1;
	b.m[1][0] = 1, b.m[1][1] = 2, b.m[1][3] = 1;
	b.m[2][0] = 1, b.m[2][2] = 2, b.m[2][3] = 1;
	b.m[3][1] = 1, b.m[3][2] = 1, b.m[3][3] = 2;
	while (n)
	{
		if (n & 1)
			a = mul(a, b);
		n >>= 1;
		b = mul(b, b);
	}
	M res;
	res.m[0][0] = 2, res.m[1][0] = 1, res.m[2][0] = 1;
	res = mul(a, res);
	cout << res.m[0][0] % mod << endl;
}
int main(){
	string s;
	while (cin >> s)
	{
		ll b = 0;
		int len = sz(s);
		for (int i = 0; i < len; i++)
		{
			b = (b * 10 + s[i] - '0') % (mod - 1);
		}
		fpow(b - 1);
	}
	return 0;
}