吉首大学重现赛 A:SARS病毒（矩阵快速幂 + 降幂）
登录—专业IT笔试面试备考平台_牛客网
https://ac.nowcoder.com/acm/contest/992/A
这题布吉岛为啥可以降幂
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;
}
