矩阵

定义

只有(A的行数)和(B的列数)相等，这两个矩阵才可以相乘

设(A)是一个(n imes p)的矩阵，(B)是一个(p imes m)的矩阵。

若(A imes B=C)，那么(C)肯定是一个(n imes m)的矩阵。

矩阵(C)中的​元素可以表示为

[C_{i,j}=sum_{k=1}^PA_{i,k}B_{k,j} ]

举个栗子：

[left[egin{matrix}3&3&7&8 \end{matrix} ight] imesleft[egin{matrix}4\5\8\1\8end{matrix} ight]=left[egin{matrix}12&15&24&3&24\12&15&24&3&24\28&35&56&7&56\32&40&64&8&64\end{matrix} ight] ]

国家级冠军的必备千位数加减！

矩阵乘法不满足交换律（不用说都知道），但是满足结合律。

也很好证明。

若(A imes B imes C=D)

设(A imes B=T)

[D_{i,j}=sum_{x=1}^qT_{i,x} imes C_{x,j}\D_{i,j}=sum_{x=1}^q(sum_{y=1}^pA_{i,y} imes B_{y,x}) imes C_{x,j}\D_{i,j}=sum_{x=1}^qsum_{y=1}^pA_{i,y} imes B_{y,x} imes C_{x,j} ]

设(A imes (B imes C)=E)

同理得

[E_{i,j}=sum_{x=1}^psum_{y=1}^qA_{i,x} imes B_{x,y} imes C_{y,j} ]

可得(D=E)

方阵

一个(n imes n)的矩阵

因为行数和列数相等，所以方阵的幂有意义。

我们就可以利用快速幂优化方阵。

。。。

优化线性递推

求斐波那契数列的第(n)项(POJ3070)

(1le nle10^{18})，对大质数取模

(f_0=0,f_1=1,f_n=f_{n-1}+f_{n-2})

我们设矩阵(A_n=left[egin{matrix}f_n,f_{n-1}end{matrix} ight])

弄一个矩阵

[left[egin{matrix}0&1\1&1end{matrix} ight] ]

(A_{n-1})乘上这玩意就是(A_n)

于是我们就可以使用矩阵乘法快速幂。

#include <cstdio>
#include <cstring>

using namespace std;
typedef long long ll;
const int SZ = 2;
const ll P = 10000;

struct Mat
{
    ll a[SZ + 5][SZ + 5];
} ys, ans;

inline Mat mul(Mat a, Mat b)
{
    Mat res;
    ll r;
    memset(res.a, 0, sizeof(res.a));
    for (int i = 1; i <= SZ; i++)
        for (int k = 1; k <= SZ; k++)
        {
            r = a.a[i][k];
            for (int j = 1; j <= SZ; j++)
                (res.a[i][j] += b.a[k][j] * r) %= P;
        }
    return res;
}

inline void qpow(ll p)
{
    for (; p; p >>= 1, ys = mul(ys, ys))
        if (p & 1) ans = mul(ans, ys);
}

void init()
{
    memset(ans.a, 0, sizeof(ans.a));
    for (int i = 1; i <= SZ; i++) ans.a[i][i] = 1;
    memset(ys.a, 0, sizeof(ys.a));
    ys.a[1][2] = ys.a[2][1] = ys.a[2][2] = 1ll;
}

int main()
{
    ll n;
    for (; scanf("%lld", &n), ~n;)
        if (n <= 1) printf("%lld
", n);
        else init(), qpow(n + 1), printf("%lld
", ans.a[1][1]);
    return 0;
}

Luogu P5110 块速递推

给出数列(a)，满足(a_0=0,a_1=1,a_n=233a_{n-1}+666a_{n-2})，求(A_n)，对(10^9+7)取模

(n<2^{64},1le Tle5 imes10^7)

(T)组询问，每个询问查询(A_n)，求所有询问答案的异或和

设矩阵(left[egin{matrix}A_{n-1}&A_nend{matrix} ight])

老套路

[left[egin{matrix}A_{n-1}&A_nend{matrix} ight]\=left[egin{matrix}A_{n-2}&A_{n-1}end{matrix} ight] imesleft[egin{matrix}0&666\1&233end{matrix} ight] ]

但是询问数大的一批。

我们可以预处理出到(sqrt n)的答案，询问时只要将(n)拆为一个(ak+b)的数，直接(O(1))查询。

#pragma GCC optimize("inline,Ofast", 3)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")

#include <bits/stdc++.h>

using namespace std;
typedef unsigned long long llu;
typedef long long ll;
const int N = 32000, P = 1e9 + 7;

struct Mat
{
    int a[2][2];
    inline Mat operator* (const Mat &t) const
    {
        Mat res;
        res.a[0][0] = (1ll * a[0][0]* t.a[0][0] + 1ll * a[0][1] * t.a[1][0]) % P;
        res.a[0][1] = (1ll * a[0][0]* t.a[0][1] + 1ll * a[0][1] * t.a[1][1]) % P;
        res.a[1][0] = (1ll * a[1][0]* t.a[0][0] + 1ll * a[1][1] * t.a[1][0]) % P;
        res.a[1][1] = (1ll * a[1][0]* t.a[0][1] + 1ll * a[1][1] * t.a[1][1]) % P;
        return res;
    }
} m1[N + 5], m2[N + 5], s;
llu SA, SB, SC;

llu Rand()
{
    SA ^= SA << 32, SA ^= SA >> 13, SA ^= SA << 1;
    llu t = SA;
    SA = SB, SB = SC, SC ^= t ^ SA;
    return SC;
}

int main()
{
    s = {233, 666, 1, 0}, m1[0] = m2[0] = {1, 0, 0, 1}; 
    for (int i = 1; i <= N; i++) m1[i] = m1[i - 1] * s;
    s = m1[N];
    for (int i = 1; i <= N; i++) m2[i] = m2[i - 1] * s;
    int T;
    scanf("%d%llu%llu%llu", &T, &SA, &SB, &SC);
    int ans = 0;
    for (int n; T--;)
        n = (Rand() - 1) % (P - 1), ans ^= (m2[n / N] * m1[n % N]).a[0][0];
    return printf("%d
", ans), 0;
}
```cpp