gym-103708D Different Pass a Ports

Different Pass a Ports

矩阵快速幂 模板

图的邻接矩阵的 \(k\) 次幂就是从图上所有点走 \(k\) 步的方案数

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int maxn = 110;
const ll mod = 1e9 + 7;

struct node
{
    ll array[maxn][maxn];
    int x, y;
    node(){x = 0, y = 0;}
    node(int _x, int _y) {x = _x; y = _y;}
    void init(int a)
    {
        for(int i=1; i<=x; i++)
            for(int j=1; j<=y; j++)
                array[i][j] = (i == j) * a;
    }
    node operator *(const node& a) const
    {
        node ans(x, a.y);
        ans.init(0);
        for(int i=1; i<=x; i++)
        {
            for(int j=1; j<=a.y; j++)
            {
                for(int k=1; k<=y; k++)
                {
                    ans.array[i][j] += array[i][k] * a.array[k][j] % mod;
                }
                ans.array[i][j] %= mod;
            }
        }
        return ans;
    }
};

node qpow(node x, int n)
{
    node ans(x.x, x.y);
    ans.init(1);
    while(n)
    {
        if(n & 1) ans = ans * x;
        n >>= 1;
        x = x * x;
    }
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
    node x(n, n);
    x.init(0);
    while(m--)
    {
        int a, b;
        cin >> a >> b;
        x.array[a][b]++;
        x.array[b][a]++;
    }
    node last = qpow(x, k);
    ll ans = 0;
    node now(1, n);
    now.init(1);
    now = now * last;
    for(int i=1; i<=n; i++)
        ans += now.array[1][i];
    ans %= mod;
    cout << ans << endl;
    return 0;
}