Description

题目链接

题目大意:求图上从 $1$ 走到 $n$,长度为 $t$ 的路径数量。$1 \le n \le 10, 1 \le t \le 10^9$。

Solution

如果是 $t$ 较小的情况,我们可以直接 DP,但是这里的 $t$ 非常大,且 $n$ 非常小。

这是 OI 中的一类经典题型:矩阵乘法加速图上问题。

我们先考虑弱化版的情况:每条边的边权为 $1$,现在设 $f(i, j)$ 为从 $i$ 走到 $j$ 的路径数量,枚举点 $k$,利用 Floyd 的思想和乘法原理,不难发现 $f(i, j) = \sum \limits_{1 \le k \le n} (f(i, k) \cdot f(k, j))$。

我们注意到这个式子跟矩阵乘法的形式十分相像,我们求出原图的邻接矩阵后做 $k$ 遍矩阵乘法后,矩阵中 $A_{i, j}$ 表示的就是从 $i$ 到 $j$,长度为 $k$ 的路径条数(注意这里我们所有的边权都为 $1$)。

如果边权不为 $1$ 怎么办?我们可以考虑将图分层(或者叫拆点),将图转化成边权只有 $0$ 和 $1$ 的图去求解。

设边权的值域为 $[1, m]$,该算法的时间复杂度为 $O(m^3 \log t)$。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

template <class T>
inline void read(T &x) {
    x = 0;
    int f = 0;
    char ch = getchar();
    while (!isdigit(ch))    { f |= ch == '-'; ch = getchar(); }
    while (isdigit(ch))     { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    x = f ? -x : x;
    return ;
}

typedef unsigned long long uLL;
typedef long long LL;

const int mod = 2009;
const int maxSize = 100 + 10;

struct Matrix {
    int a[maxSize][maxSize];
    int n, m;
    Matrix() {
        n = m = 0;
        memset(a, 0, sizeof(a));
    }
    friend Matrix operator * (const Matrix &a, const Matrix &b) {
        Matrix s;
        s.n = a.n, s.m = b.m;
        for (int k = 1; k <= a.m; ++k) {
            for (int i = 1; i <= a.n; ++i) {
                for (int j = 1; j <= b.m; ++j) {
                    s.a[i][j] += a.a[i][k] % mod * b.a[k][j] % mod;
                    s.a[i][j] %= mod;
                }
            }
        }
        return s;
    }
} a, ans;

int n, b;
char s[20];

int pos(int i, int j) { return i + j * n; }

int main() {
    read(n), read(b);
    a.n = a.m = ans.n = ans.m = n * 9;
    for (int i = 1; i <= n * 9; ++i)    ans.a[i][i] = 1;
    for (int i = 1; i <= n; ++i) {
        scanf("%s", s + 1);
        for (int j = 1; j <= 8; ++j)    a.a[pos(i, j)][pos(i, j - 1)] = 1;
        for (int j = 1; j <= n; ++j) {
            if (s[j] - '0') {
                a.a[i][pos(j, s[j] - '0' - 1)] = 1;
            }
        }
    }
    while (b) {
        if (b & 1)    ans = ans * a;
        a = a * a;
        b >>= 1;
    }
    printf("%d\n", ans.a[1][n]);
    return 0;
}
Last modification:September 2nd, 2021 at 02:06 am