路径数量统计

itdef / 2024-09-04 / 原文

// 路径数量统计.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

/*
http://oj.daimayuan.top/course/22/problem/1044

题目描述
给你一张有向图，图中可能存在重边和自环，请求出从点 u
 出发经过恰好 k
 条边后到达点 v
 的通路的条数。由于答案可能很大，请输出答案模 109+7
。

输入格式
第一行两个整数 n,m
 分别表示点数和边数。

接下来 m
 行，每行两个整数 x,y
，表示从 x
 到 y
 有一条有向边。

最后一行三个整数 u,v,k
 表示询问。

输出格式
一行一个数表示答案模 109+7
 的结果。

样例输入
2 3
1 2
2 1
1 1
1 2 3
样例输出
2
数据范围
对于 100%
 的数据，保证 1≤n≤200,1≤m≤104,1≤x,y,u,v≤n,1≤k≤109
。
*/

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cstring>


using namespace std;

const int N = 200;
const int P = 1000000007;
int n, m, u, v, k;
long long f[N+1],a[N+1][N+1];

void aa() {
    long long w[N + 1][N + 1];
    memset(w, 0, sizeof w);
    for (int i = 1; i <= n; i++) {
        for (int k = 1; k <= n; k++) {
            if(a[i][k])
                for (int j = 1; j <= n; j++) {
                    if (a[k][j]) {
                        w[i][j] += a[i][k] * a[k][j], w[i][j] %= P;
                    }
                }
        }
    }

    memcpy(a, w, sizeof a);
}

void fa() {
    long long w[N + 1];
    memset(w, 0, sizeof w);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            w[i] += f[j] * a[j][i], w[i] %= P;
        }
    }

    memcpy(f, w, sizeof w);
}

void matrixpow(long long k) {
    for (; k; k >>= 1) {
        if (k & 1) 
            fa();
        aa();
    }
}


int main()
{
    scanf("%d%d",&n,&m);
    for (int i = 1; i <= m; i++) {
        int x, y;
        scanf("%d%d",&x,&y);
        ++a[x][y];
    }
    scanf("%d%d%d", &u, &v, &k);
    f[u] = 1;
    matrixpow(k);
    printf("%lld\n",f[v]);

}