牛客小白月赛13 E（图、矩阵幂）

AC通道

如果建立第一天某点到某点有几条路的矩阵，做k次矩阵乘就是第k天某点到某点有几条路。统计即可。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 101, mod = 1e9 + 7;

int N, M, K, S, ans;

struct Matrix {

    int v[maxn][maxn], n;

    Matrix(int n) { memset(v, 0, sizeof v); this->n = n; }

    Matrix operator * (const Matrix &A) const {

        Matrix ret(n);

        for (int i = 0; i < n; i++)

            for (int j = 0; j < n; j++)

                for (int k = 0; k < n; k++)

                    ret.v[i][j] = ((ll)ret.v[i][j] + (ll)v[i][k] * A.v[k][j] % mod) % mod;

        return ret;

    }

    Matrix operator ^ (int b) const {

        Matrix ret(n);

        Matrix A = *this;

        for (int i = 0; i < n; i++)

            ret.v[i][i] = 1;

        for (; b; b >>= 1) {

            if (b & 1)    ret = ret * A;

            A = A * A;

        }

        return ret;

    }

};

int main() {

    scanf("%d %d %d %d", &N, &M, &K, &S);

    Matrix A(N);

    for (int i = 0; i < M; i++) {

        int u, v;

        scanf("%d %d", &u, &v);

        A.v[--u][--v]++;

    }

    A = A ^ K;

    S--;

    for (int i = 0; i < N; i++) {

        if (i != S) {

            ans = ((ll)ans + A.v[S][i]) % mod;

        }

    }

    printf("%d\n", ans);

    return 0;

}

巴特西

牛客小白月赛13 E（图、矩阵幂）

最新文章

热门文章