欢乐赛#40 T3 题解

矩阵快速幂解法：

#include <iostream> 
using namespace std; 
const int MOD = 998244353; 
// 快速幂函数，用于计算 a 的 b 次方对 MOD 取模的结果 
long long quickPow(long long a, long long b) { 
    long long res = 1; 
    while (b > 0) { 
        if (b & 1) { 
            res = res * a % MOD; 
        } 
        a = a * a % MOD; 
        b >>= 1; 
    } 
    return res; 
}
int main() { 
    int n; 
    cin >> n; 
    long long ans = quickPow(114514, n); 
    cout << ans << endl; 
    return 0; 
}
//快速幂的工作原理:将指数n分解成二进制形式，然后利用指数的二进制每一位来分解计算，从而将时间复杂度从O(n)降低到O(log n)。这样可以高效处理大指数的情况。

因为114514写全过大，所以要用矩阵快速幂.jpg