快速幂 & 矩阵运算

1 模板

注意开 long long

int qpow(int x, int y)
{
    int ans = 1;
    while (y)
    {
        if (y % 2)
            ans = (ans * x) % p;
        x = (x * x) % p;
        y /= 2;
    }
    return ans;
}

2 矩阵计算

![[../../../../images/Z-attachment/屏幕截图 2023-11-21 183403.png]] ## 3 示例: P1962 斐波那契数列 - 洛谷计算斐波那契数列，\(\Huge{n \le 2^{63}}\) 可得:

\(\begin{aligned} \begin{bmatrix}F_n\\ F_{n+1}\end{bmatrix} &= A\begin{bmatrix}F_{n-1}\\ F_n\end{bmatrix}=A^2\begin{bmatrix}F_{n-2}\\ F_{n-1}\end{bmatrix}=...&=A^{n-1}\begin{bmatrix}F_1\\ F_2\end{bmatrix}=A^{n-1}\begin{bmatrix}1\\ 1\end{bmatrix} \end{aligned}\) , \(A=\begin{bmatrix}0 &1\\ 1 & 1\end{bmatrix}\)

TI:"矩阵运算|快速幂"

#include <cstdio>
#define MOD 1000000007
typedef long long ll;

struct matrix
{
    ll a1, a2, b1, b2;
    matrix(ll a1, ll a2, ll b1, ll b2) : a1(a1), a2(a2), b1(b1), b2(b2) {}
    matrix operator*(const matrix &y)
    {
        matrix ans((a1 * y.a1 + a2 * y.b1) % MOD,
                   (a1 * y.a2 + a2 * y.b2) % MOD,
                   (b1 * y.a1 + b2 * y.b1) % MOD,
                   (b1 * y.a2 + b2 * y.b2) % MOD);
        return ans;
    }
};

matrix qpow(matrix a, ll n)
{
    matrix ans(1, 0, 0, 1); //单位矩阵
    while (n)
    {
        if (n & 1)
            ans = ans * a;
        a = a * a;
        n >>= 1;
    }
    return ans;
}

int main()
{
    ll x;
    matrix M(0, 1, 1, 1);
    scanf("%lld", &x);
    matrix ans = qpow(M, x - 1);
    printf("%lld\n", (ans.a1 + ans.a2) % MOD);
    return 0;
}

4 练习: P1939 矩阵加速（数列） - 洛谷

已知一个数列 \(a\)，它满足：

\[ a_x= \begin{cases} 1 & x \in\{1,2,3\}\\ a_{x-1}+a_{x-3} & x \geq 4 \end{cases} \]

求 \(a\) 数列的第 \(n\) 项对 \(10^9+7\) 取余的值。

对于 \(100\%\) 的数据 \(1 \leq T \leq 100\)，\(1 \leq n \leq 2 \times 10^9\)。

找出 \(A\) 矩阵即可。不一样的地方是 \(A\) 矩阵是 3 维的。 ![[../../../../images/Z-attachment/{222E6BF3-59E1-4bad-8B4A-3D65C9496B64}.png]]

5 练习： [[B3646 数列前缀和 3 - 洛谷]]

链接