要想明白这题首先要学习矩阵快速幂嗷，先学一下矩阵快速幂再来看这篇题解 没学过的可以看这里https://ac.nowcoder.com/acm/problem/226821
乍一看我们这题不是乘法递推吗，好像没有有关加法的线性递推式子，这还怎么用矩阵快速幂加速计算 没办法，那我们写几项看看找找规律 假设数列G前n项的乘积称为Sn，
S1 = G1,
S2 = G1 * G2,
S3 = G1^2 * G2^2,
S4 = G1^3 * G2^4,
S5 = G1^5 * G2^7,
S6 = G1^8 * G2^12
到这里就能找到幂次上的规律了，对于Sn = G1^an * G2^bn, S(n+1) = G1^a(n+1) * G2^b(n+1), S(n+2) = G1^a(n+2) * G2^b(n+2) 这三项来看，不难发现有b(n+2) = a(n+1) + b(n+1), a(n+2) = a(n+1) + an，这样就有线性递推式了，那我们就可以去构造矩阵来使用矩阵快速幂了，我们先来构造矩阵：
用于矩阵快速幂的就是中间的矩阵
但是！！！有一件事需要注意
左侧的原矩阵我们从上到下依次填入a2 = 1，a3 = 2，b3 = 2，在乘以构造的矩阵的n - 3次幂之后得到的答案矩阵从上到下依次为a(n-1), an, bn，将an与bn取出进行最后一步
Sn = G1^an * G2^bn,写一次快速幂就解决了（别忘了这里的模数变回998244353了）
最后输出Sn的值即可
代码如下：
using namespace std;
#define endl '\n'
#define debug(x) cerr << #x << ": " << x << '\n';
// #define int long long
#define ctz __builtin_ctzll // 返回二进制表示中末尾连续0的个数
#define clz __builtin_clzll // 返回二进驻表示中先导0的个数
#define count1 __builtin_popcountll // 返回二进制表示中1的个数
// 上面仨不是ll的时候记得调整
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int N = 2e5 + 10;
const double EPS = 1e-6;
// const ll MOD = 1e9 + 7;
ll MOD = 998244353;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll dir[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
ll dirr[8][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}, {1, 1}, {1, -1}, {-1, -1}, {-1, 1}};
void LiangBaiKai()
{
}
template <class T> // 定义矩阵乘法
vector<vector<T>> operator*(const vector<vector<T>> &a, const vector<vector<T>> &b)
{
int n = a.size(), m = b[0].size(), l = a[0].size();
vector ans(n, vector<T>(m));
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
for (int k = 0; k < l; k++)
ans[i][j] = (ans[i][j] + a[i][k] * b[k][j]) % MOD;
}
}
return ans;
}
ll qpoww(ll a, ll b) // 用于整数的快速幂计算
{
a %= MOD;
ll x = 1;
while (b)
{
if (b & 1)
x = x * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return x;
}
void Aiden()
{
ll m, n, k, sum = 0, ans = 0, num = 0, mi = INF, ma = -INF, cnt = 0, x, y, len, t, l, r, cur;
string s1, s2;
cin >> n;
if (n == 1) // 特判n = 1的情况
{
cout << 2 << endl;
return;
}
if (n == 2) // 特判n = 2的情况
{
cout << 6 << endl;
return;
}
MOD--; // 算指数的时候记得模数要减1
vector a(3, vector<ll>(3)), an(3, vector<ll>(3));
a = {{0, 1, 0}, {1, 1, 0}, {0, 1, 1}}; // 构造要进行矩阵快速幂的原始矩阵
for (ll i = 0; i < 3; i++) // 初始化单位矩阵
an[i][i] = 1;
auto qpow = [&](vector<vector<ll>> &a, ll p) -> void // 矩阵的快速幂计算(定义矩阵乘法的时候里面自带了取模，所以矩阵快速幂里不用写取模)
{
while (p)
{
if (p & 1)
an = an * a;
a = a * a;
p >>= 1;
}
};
qpow(a, n - 3);
vector b(3, vector<ll>(1));
b = {{1}, {2}, {2}};
an = an * b; // 得到答案矩阵
l = an[1][0]; // 得到G1与G2的指数
r = an[2][0];
ans = 1; // 初始化答案为1
MOD++; // 前面指数减得1记得加回来
ans = ans * qpoww(2, l) % MOD * qpoww(3, r) % MOD; // 对G1和G2用快速幂乘出答案
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
LiangBaiKai();
int _ = 1;
// cin >> _;
while (_--)
Aiden();
return 0;
}
/*
@@@@@@
@@@@@@@@@@
@@@@@@@@@@@@@
@@@@@@@@@@@@@@@
@@@@@@@@@@@
@@@@
@
@@@@@@@@@@ @@ @@@@@@@@@@@@
@@@@@ @ @@@@@
@@@ @ @@@
@@@ @@ @@@
@@ @@@
@@ @@
@@ @@
@@ @@
@ @@
@ @@@@@@@@ @@
@ @@@ @@@@@@@@@ @
@@ @@@@@@@ @@@@@@@@ @@@@@@ @
@ @@@@@@@@@@@@@@@@@@@@@@@@@@ @@
@ @@@@@@@@@@@ @@@@@@@@@@@ @
@@@@@@@@@@@@@ @@@@@@@@@@@@@@ @ @@@@@@ @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@ @@@@@@ @@@ @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@ @@@ @@@ @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@
@@@@@@ @@@@@@@@@@ @@@@@@@@@@@@@@ @@
@@@@@ @@@@@@@ @@@@@@ @@ @@@@@@@@@@@ @@@
@@@@@ @@@@@@@@ @@@@ @@@@@@@ @@@@@@@@@@@ @@
@@@@@@ @@@@@@@ @@@@@ @@@@@@@ @@@@@@@@@@@@ @@@@@@@
@@@@@@@ @ @@@@@@ @@@@@@@ @@@@@@@@@@@@@@@@ @@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@ @ @@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@ @@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @ @ @ @@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @ @@@@@ @ @@@@ @ @@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@ @@ @@ @@@ @@@@@ @@@@@@@@@@
@@@@@@@ @@@@@@@@@@@@@@ @@@@@@ @@@@@ @ @@@@@@@@
@@@@@@ @@@@@@@@@@@ @ @@@@@@@@
@@@@ @@@@@@@@ @@ @@@@@@@
@@ @@ @@@@@
@@@ @@
@@@ @@@
@@@@@@@@@@@@ @@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
*/
京公网安备 11010502036488号