TechFUL: かわいいは罪 in グラフ

TechFUL TechFUL: 上級 グラフ 行列 行列累乗

問題概要

N 頂点 M 辺の重み付き無向グラフが与えられる．

i 番目の辺は頂点 a_{i} と頂点 b_{i} を結んでおり、重みは c_{i} である．

グラフは連結で、自己ループや多重辺は存在しない．

以下のクエリに答えよ．

  • 頂点 x から t 本の辺を移動して頂点 y に移動したとき、通った t 本の辺の重みの積を「かわいい度」と定義する． 頂点 x から頂点 y へ t 本の辺を辿って着くような全ての移動方法のかわいい度の総和を求めよ．

https://techful-programming.com/user/practice/problem/coding/11282

制約

  • 2 \le N \le 50

  • 1 \le M \le \frac{N(N - 1)}{2}

  • 1 \le a_{i} \lt b_{i} \le N

  • 1 \le c_{i} \le 10^{5}

  • 1 \le Q \le 10

  • 1 \le x_{i}, y_{i} \le N

  • 1 \le t_{i} \le 10^{5}

  • (a_{i}, b_{i}) \neq (a_{j}, b_{j}) \; (i \neq j)

考えたこと．

グラフの遷移を扱う問題なので行列累乗で解けないか考えてみる．

次のような行列を定義する．

  • G_{u, v} := 頂点 u から頂点 v を繋ぐ辺が存在しないなら 0, 存在するならその辺の重み

i 回の移動で頂点 u に辿り着く全ての移動方法のかわいい度の総和を dp_{i}(u) とする．

このとき、以下の漸化式が成り立つ．

  • dp_{i+1}(v) = \sum_{1 \le u \le N} G_{u, v} \cdot dp_{i}(u)

よって、 dp_{i} を長さ N の列ベクトルと考えると、

  • dp_{i+1} = G \, dp_{i}

と表せることから、 dp_{t} は次の式で求められる．

  • dp_{t} = G^{\,t} \, dp_{0}

dp_{t} を dp_{0}(x) = 1, dp_{0}(*) = 0 で上式に従って計算すれば、 dp_{t}(y) が答えになる．

計算量は O(N^{3} Q \log t) 時間である．

行列累乗については以下を参照．

#include <bits/stdc++.h>
using namespace std;

using vec = vector<long long>;
using Matrix = vector<vec>;
const int MOD = 1000000007;

// 行列同士の積
Matrix mul(const Matrix& A, const Matrix& B) {
    assert(A.size() > 0 && A[0].size() == B.size());
    Matrix C(A.size(), vec(B[0].size(), 0));
    for (int i = 0; i < A.size(); ++i) {
        for (int j = 0; j < B[0].size(); ++j) {
            for (int k = 0; k < A[i].size(); ++k) {
                C[i][j] += A[i][k] * B[k][j] % MOD;
                C[i][j] %= MOD;
            }
        }
    }
    return C;
}

// 行列の累乗
Matrix pow(Matrix A, int n) {
    Matrix B(A.size(), vec(A[0].size(), 0));
    for (int i = 0; i < A.size(); ++i) {
        B[i][i] = 1;
    }
    while (n > 0) {
        if (n & 1) B = mul(B, A);
        A = mul(A, A);
        n >>= 1;
    }
    return B;
}

int N, M, Q;
Matrix G;

int main() {
    cin >> N >> M;
    G.resize(N, vec(N, 0));
    for (int i = 0; i < M; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        G[a][b] = G[b][a] = c;
    }
    cin >> Q;
    for (int i = 0; i < Q; ++i) {
        int x, y, t;
        cin >> x >> y >> t;
        x--; y--;
        cout << pow(G, t)[y][x] << endl;
    }
}

類題