链接：https://ac.nowcoder.com/acm/contest/549/E
来源：牛客网

小A来到了一个陌生的城镇，这个城镇与其它城镇之间构成了集群。城镇之间的路径都是单向的，而小A每一天都能由一个城镇走到另外一个城镇。小A将会连续走k天，直到抵达某个城镇。也许他并不能走到这个城镇，那么可以认为不存在这样的路径，也就是路径数为0。否则就会有若干条路径可以抵达某个城镇。现在他想知道，如果他从给定某个城市出发，k天之后到达其它城镇的路径的总和是多少。数据不保证没有重边，也就是说可能每一天从一个城镇到另外一个城镇之间会有多条路径。路径总和可能会非常大，对答案模上1000000007。

思路：矩阵表示第一天的时候u到v有多少条路径，然后直接做矩阵k次幂就能得到k天从u到v的路径数，最后统计一下就可以了。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 105;
ll mp[maxn + 5][maxn + 5];
ll Ans[maxn + 5][maxn + 5];
const ll mod = 1e9 + 7;
 
void qpow(ll a[maxn + 5][maxn+5], ll b[maxn+5][maxn+5], ll n) {
    int c[maxn+5][maxn+5];
    for(ll i = 1; i <= n; i++) {
        for(ll j = 1; j <= n; j++) {
            c[i][j] = 0;
            for(int k = 1; k <= n; k++) {
                c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % mod;
            }
        }
    }
    for(ll i = 1; i <= n; i++) {
        for(ll j = 1; j <= n; j++) {
            a[i][j] = c[i][j];
        }
    }
}
 
int main() {
    ll n, m, s, k;
    ll u, v;
    scanf("%lld%lld%lld%lld", &n, &m, &k, &s);
    for(ll i = 1; i <= m; i++) {
        scanf("%lld%lld", &u, &v);
        mp[u][v] += 1;
    }
    for(ll i = 1; i <= n; i++) {
        Ans[i][i] = 1;
    }
    while(k) {
        if(k&1) {
            qpow(Ans, mp, n);
        }
        qpow(mp, mp, n);
        k >>= 1;
    }
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        if (i == s) {
            continue;
        }
        ans += Ans[s][i];
        ans %= mod;
    }
    printf("%lld\n", ans);
    return 0;
}