Matrix Multiplication

递推数列

路径计数

给定一张图,处理形如 “从 \(u\)\(v\) 恰好经过 \(k\) 条边的路径条数” 的计数问题。

\(f[u][v][k]\) 表示从 \(u\)\(v\) 恰好经过 \(k\) 条边的路径条数,设 \(e[u][v]=1\) 表示存在一条从 \(u\)\(v\) 的边,有转移 \[ f[u][v][k] = \sum_{1\le w\le n} f[u][w][k-1]\cdot e[w][v] \] 这是一个典型的矩阵乘法,设 \(F[k]\) 表示 \(k\) 步的 \(f\) 数组,有 \(F[k]=E^k (k\ge 0)\)

广义矩阵乘法

使用矩阵乘法来维护的要求有两个:

  1. 运算结果满足对应代数表达式;
  2. 满足结合律(用于快速幂加速)。

比较严谨的结论是:矩阵乘法可以处理的代数结构为半环 \((A,+,\cdot)\) ,即满足:

  • \((A,+)\) 为带有单位元 \(0\) 的交换幺半群(单位元,结合律,交换律);
  • \((A,\cdot\ )\) 为带有单位元 \(1\) 的幺半群(单位元,结合律);
  • 乘法对加法同时有左、右分配律;
  • 加法单位元 \(0\) 抵消乘法。

In general, if the addition and multiplication satisfies the axioms of semi-ring, then the associativity of multiplication of matrices holds, enabling us to optimize DP with the matrix exponentiation like described above.

A semi-ring is a set \(A\) equipped with two binary operations, addition \(+\) and multiplication \(\cdot\) , such that all the following properties is satisfied:

  • \((A,+)\) is an commutative monoid; i.e. it satisfies the following three conditions:

    • The associativity of \(+\) holds. That is, for any \(a, b, c \in A\), it holds that \((a+b)+c=a+(b+c)\).
    • There exists an identity 0 of \(+\). That is, there exists \(0 \in A\) such that \(a+0=0+a=a\).
    • The commutativity of \(+\) holds. That is, for any \(a, b \in A\), it holds that \(a+b=b+a\).
  • \((A, \cdot)\) is a monoid; i.e. it satisfies the following two conditions:

    • The associativity of \(\cdot\) holds. That is, for any \(a,b,c\in A\), it holds that \((a \cdot b) \cdot c=a \cdot(b \cdot c)\) .

    • There exists an identity 1 of \(\cdot\). That is, there exists \(1 \in A\) such that \(a \cdot 1=1 \cdot a=a\).

  • \(+\) and \(\cdot\) satisfies the following distributive property holds:

    • For any \(a, b, c \in A\), it holds that \(a \cdot(b+c)=a \cdot b+a \cdot c\) .

    • For any \(a, b, c \in A\), it holds that \((a+b) \cdot c=a \cdot c+b \cdot c\) .

  • For all \(a \in A\), it holds that \(0 \cdot a=a \cdot 0=0\).

一些例子

注意,使用广义矩阵乘法时,初始矩阵和单位矩阵对应的 \(0\)\(1\) 自然的应当使用广义的 \(0\)\(1\)

ID \(A\) \(+\) \(0\) \(\cdot\) \(1\)
1 \(\mathbb{R}\) \(\min\) \(+\infty\) \(\max\) \(-\infty\)
2 \(\mathbb{R}\) \(\max\) \(-\infty\) \(\min\) \(+\infty\)
3 \(\mathbb{R}\cup \{-\infty \}\) \(\max\) \(-\infty\) ordinary addition \(+\) \(0\)
4 \(\mathbb{R}\cup \{+\infty \}\) \(\min\) \(+\infty\) ordinary addition \(+\) \(0\)
5 \(\forall n\in \mathbb{N^+},\ [0,2^n)\cap \mathbb{N}\) bitwise OR \(0\) bitwise AND \(2^n-1\)
6 \(\forall n\in \mathbb{N^+},\ [0,2^n)\cap \mathbb{N}\) bitwise AND \(2^n-1\) bitwise OR \(0\)
7 \(\forall n\in \mathbb{N^+},\ [0,2^n)\cap \mathbb{N}\) bitwise XOR \(0\) bitwise AND \(2^n-1\)

ABC 236 G - Good Vertices

有一张无向图,开始没有边,第 \(1\sim m\) 秒每秒加一条边 \(u_i,v_i\)

询问每个点 \(u\) ,询问最早的时刻,图中存在一条长度恰好为 \(l\) 的从 \(1\)\(u\) 的路径。

将边加入的时间设为边权,即 \(e[u_i][v_i]=i\) ,问题改为长度为 \(l\) 的路径上最大边权最小是多少。

\(f[u][v][k]\) 表示恰好经过 \(k\) 条边从 \(u\)\(v\) ,路径上的最大边权最小值。

枚举第 \(k-1\) 步(即 \(v\) 前一个)走到的点 \(w\) ,转移方程为:\(f[u][v][k] = \min_{1\le w\le n} \big\{ \max (f[u][w][k-1], e[w][v])\big\}\)

只看一步转移,发现这是一个加法为 \(\min\) ,乘法为 \(\max\) 的矩阵乘法,检验:

  • 加法 \(\min\) 的单位元为 \(+\infty\) ,满足结合律交换律;
  • 乘法 \(\max\) 的单位元为 \(-\infty\) ,满足结合律;
  • 左分配律:\(\max(a,\min(b,c)) = \min(\max(a,b),\max(a,c))\) ,由于 \(\max\) 有交换律所以右分配律自然成立;
  • 加法单位元抵消乘法: \(\max(+\infty, x) = +\infty\)

所以可以用矩阵维护,对邻接矩阵做此时的矩阵快速幂即可,当然这个问题可以询问有向图以及任意点对。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int rd() {
int x = 0;
bool f = 0;
char c = getchar();
for (; !isdigit(c); c = getchar()) f |= (c == '-');
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return f ? -x : x;
}

#define N 101

int n, m, l;

inline int min(const int &a, const int &b) {return a < b ? a : b;}

inline int max(const int &a, const int &b) {return a < b ? b : a;}

struct matrix {
int a[N][N];
matrix(bool id = 0) {
memset(a, 0x3f, sizeof(a));
if (id) for (int i = 0; i < N; ++i) a[i][i] = -1e9;
}
inline matrix operator * (const matrix &obj) const {
matrix res;
for (int k = 1; k <= n; ++k)
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
res.a[i][j] = min(res.a[i][j], max(a[i][k], obj.a[k][j]));
return res;
}
inline matrix fpow(int t) const {
matrix res(1), x = *this;
for (; t; t >>= 1, x = x * x)
if (t & 1) res = res * x;
return res;
}
} A, res;

int main() {
n = rd(); m = rd(); l = rd();
for (int i = 1; i <= m; ++i) {
int u = rd(), v = rd();
A.a[u][v] = min(A.a[u][v], i);
}
res = A.fpow(l);
for (int i = 1; i <= n; ++i)
printf("%d ", res.a[1][i] > m ? -1 : res.a[1][i]);
return 0;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!