碎碎念

今天的模拟考$T2$写对了递推式但$MLE$惨遭爆$0$。

我是真的菜随手开了个$10^8$的$long long$数组$QAQ$

数组改小后只有$60$,在众大佬的点拨下才发现要用矩阵加速。

其实就算考试的时候想到了也没用哈哈哈哈因为我写不来了。

于是在这个宁静的夜晚,伴随着艾强吃泡面的啧啧声,

菜鸡开始复习矩阵(嗯,是的)。

矩阵啊矩阵

基本定义

矩阵就是一个数字阵列,例如:

$A=\begin{bmatrix}a_{11}&a_{12}&a_{13}\\a_{21}&a_{22}&a_{23}\end{bmatrix}=\begin{bmatrix}1&2&3\\4&5&6\end{bmatrix}$

这是一个$2*3$矩阵$A=(a_{ij})$,其中$i=1,2$,$j=1,2,3$。

第$i$行第$j$列的元素用$a_{ij}$表示。

一般用大写字母表示矩阵,小写字母表示它的元素。

矩阵$A$的转置矩阵$A^T$通过把行变列得到:第$1$行变成第$1$列、第$2$行变成第$2$列……。

$$ A^T=\begin{bmatrix}1&4\\2&5\\3&6\end{bmatrix} $$

在程序设计中,矩阵实质就是一个二维数组!

矩阵加减法

矩阵加减法的定义为两个矩阵对应行列元素进行加或减。

所以,两个行数、列数分别相等,加减法才有定义。

$$ \begin{bmatrix}5&4&3\\2&1&3\end{bmatrix}+\begin{bmatrix}2&4&3\\2&5&6\end{bmatrix}=\begin{bmatrix}8&7&6\\4&6&9\end{bmatrix} $$

$$ \begin{bmatrix}5&4&3\\2&1&3\end{bmatrix}-\begin{bmatrix}2&4&3\\2&5&6\end{bmatrix}=\begin{bmatrix}3&0&0\\0&1&0\end{bmatrix} $$

矩阵乘法

在矩阵$A$的列数与矩阵$B$的行数相等,则可以定义矩阵乘法$C=AB$

①如果$A$是一个$m\times n$的矩阵,$B$是一个$n\times p$的矩阵,则$C$是一个$m\times p$的矩阵。

②其中乘积矩阵$C$的第$i$行第$j$列元素$C_{ij}$满足:$C_{i,j}=\sum_{k=1}^ra_{i,k}\times b_{k,j}$

struct matrix{
    int row,col;
    ll v[size][size];
    matrix(){memset(v,0,sizeof(v));}
    matrix operator*(const matrix &b)const{
        matrix c;
        c.row=row,c.col=b.col;
        for(int i=1;i<=c.row;i++)
        for(int j=1;j<=c.col;j++)
        for(int k=1;k<=col;k++){
            c.v[i][j]+=v[i][k]*b.v[k][j];
            c.v[i][j]%=mod;
        }
        return c;
    }
};
矩阵乘法加速递推

对于递推式$a[x]=a[x-1]+a[x-3] (x>3)$

我们先要明确目标矩阵:$\begin{bmatrix}f[i]&f[i-1]&f[i-2]\end{bmatrix}$

根据递推式可以得到下面三个式子:

$\begin{equation}\left\{\begin{array}{lr}f[i]=f[i-1] \times 1 + f[i-2] \times 0 + f[i-3] \times 1\\f[i-1]=f[i-1] \times 1 + f[i-2] \times 0 + f[i-3] \times 0\\f[i-2]=f[i-1] \times 0 + f[i-2] \times 1 + f[i-3] \times 0\\\end{array}\right.\end{equation}$

通过每一项的系数可以得出初始矩阵为:

$\begin{bmatrix}1&1&0\\0&0&1\\1&0&0\end{bmatrix}$

最后通过推出的矩阵进行递推(矩阵快速幂)。

void qkpow(matrix f,matrix base){
    while(n){
        if(n&1) f=f*base;
        base=base*base;
        n>>=1;
    }
    return ans; 
}

撒花★,°:.☆( ̄▽ ̄)/$:.°★