@RabbitHu 2017-08-03T01:48:55.000000Z 字数 4332 阅读 1867

矩阵乘法的4个有趣应用

笔记

Vijos 1049 送给圣诞夜的礼品

有一个编号为 1~n 的序列，提供 m 个操作，每个操作是一个序列a，表示将当前序列中的a[i]个数放在第i个位置上。从头至尾循环执行这m个操作，直到共执行了k个操作。求最后得到的序列。

~ 矩阵乘法。

0 0 1 0       1       3
1 0 0 0   *   2   =   1
0 0 0 1       3       4
0 1 0 0       4       2

首先把m个操作乘成一个矩阵，然后用快速幂求出它的 k/m 次方，再乘上剩下的前 k%m 个矩阵，得到的就是总的操作，最后再乘上 1~n 竖排排列的一个原始矩阵，得到的就是最终结果。

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int MAXN = 105;
int n, m, k;
struct matrix {
    int g[MAXN][MAXN];
    matrix(){
        memset(g, 0, sizeof(g));
    }
    matrix operator * (matrix b) {
        matrix c;
        for(int k = 1; k <= n; k++)
            for(int i = 1; i <= n; i++)
                for(int j = 1; j <= n; j++)
                    c.g[i][j] += g[i][k] * b.g[k][j];
        return c;
    }
} one, op, tp, rest, ans;
void init(){
    for(int i = 1; i <= n; i++)
        one.g[i][i] = 1;
    op = rest = one;
    for(int i = 1; i <= n; i++)
        ans.g[i][1] = i;
}
matrix qpow(matrix a, int x){
    if(x == 0) return one;
    matrix t = qpow(a, x >> 1);
    if(x & 1) return t * t * a;
    return t * t;
}
int main(){
    scanf("%d%d%d", &n, &m, &k);
    init();
    for(int i = 1; i <= m; i++){
        memset(tp.g, 0, sizeof(tp.g));
        int v;
        for(int j = 1; j <= n; j++){
            scanf("%d", &v);
            tp.g[j][v] = 1;
        }
        op = tp * op;
        if(i <= k % m)
            rest = tp * rest;
    }
    op = qpow(op, k / m);
    ans = rest * op * ans;
    for(int i = 1; i <= n; i++){
        if(i > 1) printf(" ");
        printf("%d", ans.g[i][1]);
    }
    printf("\n");
    return 0;
}

@ 矩阵乘法注意顺序。

Vijos 1067 Warcraft III 守望者的烦恼

有一排格子，一开始在第 0 个格子，每次可以往右走 1~k 步，最后都要到达第 n 个格子。问有多少种方案？

~ 类似斐波那契！

首先我们知道状态转移方程：
$dp[i] = \sum_{j=1}^{k} dp[i-j]$

构造一个这样的矩阵：

0 1 0 0 0       dp[i]       dp[i+1]
0 0 1 0 0       dp[i+1]     dp[i+2]
0 0 0 1 0   *   dp[i+2]  =  dp[i+3]
0 0 0 0 1       dp[i+3]     dp[i+4]
1 1 1 1 1       dp[i+4]     dp[i+5]

求出左边那个矩阵的 m 次方就好了！

事实上，许多递推式都可以写成矩阵乘法，例如:
$dp[i] = dp[i-4] + 3*dp[i-3] + 5*dp[i-2] - 2*dp[i-1]$

……的矩阵可以写成：

这些矩阵共同特点是右上角 (n-1)*(n-1) 的小矩阵的主对角线为 1，最后一行为递推式中对应的系数。

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
const int MO = 7777777, MAXN = 12;
int n, m; //n是技能等级, m是监狱个数 
struct matrix {
    ll g[MAXN][MAXN];
    matrix(){
        memset(g, 0, sizeof(g));
    }
    matrix operator * (matrix b) {
        matrix c;
        for(int k = 1; k <= n; k++)
            for(int i = 1; i <= n; i++)
                for(int j = 1; j <= n; j++)
                    c.g[i][j] = (c.g[i][j] + g[i][k] * b.g[k][j] % MO) % MO;
        return c;
    }
} op, ans, one;
matrix qpow(matrix a, int x){
    if(x == 0) return one;
    matrix t = qpow(a, x >> 1);
    if(x & 1) return t * t * a;
    return t * t;
}
void init(){
    for(int i = 1; i <= n; i++)
        one.g[i][i] = 1;
    for(int i = 1; i < n; i++)
        op.g[i][i + 1] = 1;
    for(int i = 1; i <= n; i++)
        op.g[n][i] = 1;
    ans.g[n][1] = 1;
}
int main(){
    scanf("%d%d", &n, &m);
    init();
    op = qpow(op, m);
    ans = op * ans;
    printf("%lld\n", ans.g[n][1]); 
    return 0;
}

Vijos 1603 迷宫

水题：有向图，求两点之间恰好走k条边能到达的路径数目。

~
一个结论：k条边路径数目 = 邻接矩阵的k次方中对应的路径数目

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
const int MAXN = 55;
int n, s, f, m, p;
struct matrix {
    ll g[MAXN][MAXN];
    matrix(){
        memset(g, 0, sizeof(g));
    }
    matrix operator * (matrix b) {
        matrix c;
        for(int k = 1; k <= n; k++)
            for(int i = 1; i <= n; i++)
                for(int j = 1; j <= n; j++)
                    c.g[i][j] = (c.g[i][j] + g[i][k] * b.g[k][j] % p) % p;
        return c;
    }
} one, ans;
void init(){
    for(int i = 1; i <= n; i++)
        one.g[i][i] = 1;
}
matrix qpow(matrix a, int x){
    matrix ans = one;
    while(x){
        if(x & 1) ans = ans * a;
        a = a * a;
        x >>= 1;
    }
    return ans;
}
int main(){
    scanf("%d", &n);
    init();
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            scanf("%lld", &ans.g[i][j]);
    scanf("%d%d%d%d", &m, &s, &f, &p);
    ans = qpow(ans, m);
    printf("%lld\n", ans.g[s][f]);
    return 0;
}

Vijos 1194 多米诺 Domino

一个长 $n$ 高 $m$ 棋盘 ( $n \le 10^9, m \le 5$ )，用 $1*2$ 的多米诺骨牌完全覆盖，问有多少种方案。

~
用二进制表示某一列每个方格被覆盖与否的情况，然后考虑用各种方式填满这一列时，下一列的情况是什么。注意：禁止在当前列竖放多米诺骨牌，因为会和这一列的另一种情况重复，但下一列可以竖放。

例如下图，中间那列是“当前列”，当前列以左已经全部填满，当前列参差不齐，当前列以右还没填。：

100           111      111
100     ->    111  or  111
110           110      111
110           110      111

将所有能转换的两种状态之间连上边（如上图 0011 可以转换为 1100 或1111），得到了一个有向图。

在这个有向图上从 1111 出发，到 1111 结束，走 n 步，方案数就是覆盖棋盘的方案数。

#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
int n, m, p, M;
const int WIDTH = 34;
struct matrix {
    ll g[WIDTH][WIDTH];
    matrix(){
        memset(g, 0, sizeof(g));
    }
    matrix(int x){
        memset(g, 0, sizeof(g));
        for(int i = 0; i < M; i++)
            g[i][i] = 1;
    }
    matrix operator * (matrix b){
        matrix c;
        for(int k = 0; k < M; k++)
            for(int i = 0; i < M; i++)
                for(int j = 0; j < M; j++)
                    c.g[i][j] = (c.g[i][j] + g[i][k] * b.g[k][j] % p) % p;
        return c;
    }
} mp;
matrix qpow(matrix a, int x){
    matrix ans(1);
    while(x){
        if(x & 1) ans = ans * a;
        a = a * a;
        x >>= 1; 
    }
    return ans;
}
// Matrix67 的神奇位运算我找不到了 -_-|||
//自己编了一个十分naive的暴力判断，也能用 
bool getbit(int num, int x){
    return num & (1 << x);
}
void init(){
    for(int i = 0; i < M; i++)
        for(int j = 0; j < M; j++){
            int ok = 1, rem = j;
            for(int k = 0; k < m; k++){
                if(!getbit(i, k)){//如果母串该位为0 
                    if(!getbit(rem, k)) ok = 0;
                    //则子串该位必为1 
                    else rem -= (1 << k);
                    //去掉这些横放造成的突起 
                }
            }
        //去掉横放突起后，剩下的都是竖放的 
            int cnt = 0;
            for(int k = 0; k < m; k++){
                if(getbit(rem, k)) cnt++;
                //数数竖放挨在一起的有多少 
                if(!getbit(rem, k)){
                    if(cnt & 1) ok = 0;
                    cnt = 0;
                }
            }
            if(cnt & 1) ok = 0;
            if(ok) mp.g[i][j] = 1;
        }
}
int main(){
    scanf("%d%d%d", &n, &m, &p);
    M = 1 << m ;
    init();
    mp = qpow(mp, n);
    printf("%lld\n", mp.g[M - 1][M - 1]);
    return 0;
}