递推数列

路径计数

给定一张图，处理形如 “从 \(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\)

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

#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;
}