NOIP2018: 二、矩阵

NOIP

---

矩阵是个什么东西

以上，跟我们今天讲的矩阵没有半毛钱关系

---

出门左拐百度百科

出门右拐wiki

对于算法竞赛（这节课）来说，我们只需要知道这么几个点：

• 长什么样
• 基本性质
• 加法乘法
• 快速幂

矩阵乘法

两个矩阵的乘法仅当第一个矩阵$A$的列数和另一个矩阵$B$的行数相等时才能相乘

定义: 如$A$是$m×n$矩阵和$B$是$n×p$矩阵，它们的乘积$C$是一个$m×p$矩阵 $C = (c_{i,j})$ ，它的一个元素：

$$c_{i,j} = a_{i,1}b_{1,j} + a_{i,2}b_{2,j}+...+a_{i,n}b_{n,j} = \sum_{r=1}^{n} a_{i, r}b{r, j}$$
并将此乘积记为: $C = AB$
例如：

$$\begin{bmatrix} 1&0 &2 \\ -1& 3 &1 \end{bmatrix} * \begin{bmatrix} 3 & 1\\ 2 & 1\\ 1 & 0 \end{bmatrix} = \begin{bmatrix} (1*3+0*2+2*1) & (1*1+0*1+2*0)\\ (-1*3+3*2+1*1) & (-1*1+3*1+1*0) \end{bmatrix} = \begin{bmatrix} 5 & 1\\ 4 & 2 \end{bmatrix}$$

矩阵的乘法满足以下运算律：
结合律： $(AB)C = A(BC)$
左分配律： $(A+B)C = AC + BC$
右分配律： $C(A+B) = CA + CB$
矩阵乘法不满足交换律。

矩阵在C++中的实现

很容易想到的，用二维数组来表示一个矩阵

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
typedef long long LL;
const LL MOD = 1000000007LL;
LL n,m;
struct matrix{
    static const int MATRIX_N = 11;
    LL a[MATRIX_N][MATRIX_N];
    int row, col;
    matrix():row(MATRIX_N),col(MATRIX_N){memset(a,0,sizeof(a));}
    matrix(int x, int y):row(x),col(y){memset(a,0,sizeof(a));}
    LL* operator [] (int x){return a[x];}
    matrix operator * (matrix x){
        matrix tmp(row, x.col);
        for(int i = 0; i < row; i++)
            for(int j = 0; j < col; j++) if(a[i][j])//稀疏矩阵优化
                for(int k = 0; k < x.col; k++) if (x[j][k]){
                    tmp[i][k] += a[i][j] * x[j][k];
                    //mult(a[i][j], x[j][k], MOD);
                    tmp[i][k] %= MOD;
                }
        return tmp;
    }
    void operator *= (matrix x){*this = *this * x;}
    matrix operator ^ (LL x){
        matrix ret(row, col);
        for (int i = 0; i < col; i++) ret[i][i] = 1;
        matrix tmp = *this;
        for (; x; x >>= 1, tmp *= tmp){if (x&1) ret *= tmp;}
        return ret;
    }
    void print(){
        for (int i = 0; i < row; i++){
            for (int j = 0; j < col; j++) printf("%lld ",a[i][j]);
            puts("");
        }
    }
};
int main() {
    LL n;
    matrix B(3, 1);
    while(scanf("%lld%lld%lld%lld", &B[0][0], &B[1][0], &B[2][0], &n) == 4) {
        matrix A(3, 3);
        A[0][0] = 0; A[0][1] = 1; A[0][2] = 0;
        A[1][0] = 0; A[1][1] = 0; A[1][2] = 1;
        A[2][0] = 0; A[2][1] = 1; A[2][2] = 1;
        A = A ^ n;
        matrix C(3, 1);
        C = A * B;
        printf("%lld\n", (C[0][0] + C[1][0] + C[2][0]) % MOD);
    }
    return 0;
}

顺带复习一下快速幂

代码一定要优雅

//快速乘法
LL fast_multi(LL m, LL n, LL mod){
    LL ans = 0;//注意初始化是0，不是1 
    n = (n % mod + mod) % mod;
    for (;n; n >>= 1){
        if (n & 1) ans = (ans + m) % mod;
        m = (m + m) % mod;//和快速幂一样，只不过这里是加 
    }
    return ans % mod;
}
LL fast_pow(LL a, LL n, LL mod){//快速幂 
    LL ans = 1;
    for (;n;n >>= 1){
        if (n & 1) ans = fast_multi(ans, a, mod) % mod;//不能直接乘 
        a = fast_multi(a, a, mod) % mod;
    }
    return ans;
}

题目长什么样

斐波那契

poj3070

求斐波那契数列第10E项的值

fib[i] = f[i-1] + f[i-2]

恐怖奴隶主

现在《炉石传说》这款卡牌游戏已经风靡全球。2015年加入环境的“黑石山的火焰”扩展带来了一个新套牌的核心卡片“恐怖的奴隶主”，而这套统治游戏的套牌叫做“奴隶战”。“恐怖的奴隶主”的登场音效“想打架吗？算我一个！”一定在所有这个时代的《炉石传说》玩家心里留下来难以磨灭的印象。
“恐怖的奴隶主”是一个有3点生命值的生物，当其在场上受到非致命伤害时（如3点生命值的奴隶主受到1点或2点伤害时，或者2点生命值的奴隶主受到1点伤害时）会召唤一个新的3点生命值的“恐怖的奴隶主”，受到致命伤害（伤害大于等于现有生命值）时则会直接死去。另外一类卡片可以使全部生物造成1点伤害（降低1点生命），被称为“旋风斩效果”。因此“恐怖的奴隶主”，在场上经过多次“旋风斩效果”就可能由一个变成很多个，同时发出那个令人恐惧的声音“所有人，都过来！”。
另一方面，《炉石传说》规定，场上最多存在7个生物，这极大地限制了“恐怖的奴隶主”“越生越多”。当一次“旋风斩效果”发生时，优先处理受到非致命伤害的“恐怖的奴隶主”，召唤新的“恐怖的奴隶主”，直到生物数量达到7个不再继续召唤新的“恐怖的奴隶主”，然后清除掉生命值降为0或0以下的“恐怖奴隶主”。如场上有7个生命值为1的“恐怖的奴隶主”，则一次“旋风斩效果”后场上有0个“恐怖的奴隶主”。又如，场上有6个生命值为3的“恐怖的奴隶主”，则一次“旋风斩效果”后场上有6个2点生命的“恐怖的奴隶主”以及1个3点生命的“恐怖的奴隶主”。又如，场上有4个1点生命的“恐怖的奴隶主”以及2个2点生命的“恐怖的奴隶主”，则一次“旋风斩效果”后场上有2个1点生命的“恐怖的奴隶主”以及1个3点生命的“恐怖的奴隶主”。
在本系列题目2中我们已经知道了如何计算多个“恐怖的奴隶主”在经历n次旋风斩效果后会剩下多少。现在游戏出现了bug，场上奴隶主的个数不再受到7个的上限限制了。场上剩下了一些1点生命，一些2点生命，一些3点生命的奴隶主，现在问这些奴隶主经过n次旋风斩效果，场面会变成什么样子。

Input
有多组数据。
每组数据一行，hp1,hp2,hp3,n(0<=hp1,hp2,hp3<=10^9,0<=n<=10^6)
分别代表1点生命，2点生命，3点生命的奴隶主个数，以及之后旋风斩次数。

Output
每组用一行输出最终总的奴隶主个数（结果对1000000007取模），格式见样例。

Sample Input
1 1 1 3
3 3 3 2
Sample Output
10
18

脑洞

poj3318

给矩阵 $A,B,C$,问是否$AB = C$

作业和例题