link

题意：

小 T 迷失在了一个有 n 个点的群岛上。
初始时他在 1 号岛，他要通过架在岛间的 m 座双向桥，在正好过 k 座桥时达到 n 号岛的大门。
这些桥中有若干座附魔桥。当小 T 经过一座附魔桥时，如果他身上没有附魔标记则被标记，如果他身上已有附魔标记则标记消失。

大门只会在他身上有附魔标记时才会开启，只有这样他才能逃离。

小 T 迷失在了群岛之间，他每次会等概率随机挑选一座与他所在岛屿相连的桥走。小 T 向你询问他能逃离的概率。

保证图无自环无重边。

分析：

用 \(A [ s ] [ i ] [ j ] [ w ]\)表示从\(i\)岛恰好经过 \(2^s\)条边到达 \(j\)岛且状态为 \(w\)时的概率。
题目中 \(k≤10^6\)，所以 \(s\)最大不超过20，从低到高枚举 \(s\)，并利用Floyd更新 \(A\)即可。最后从\(A\)中凑出 \(k\)条边的值即可。
用背包二进制优化即可将步数优化掉\(k=1e^6\)然后每次维护是否是附魔状态。
或者直接利用快速幂来更新 \(A\)的同时，求出答案。

ll qpow(ll a, ll b)
{
    ll ans = 1;
    while(b)
    {
        if(b & 1) ans = ans * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return ans;
}

int n;
ll A[22][110][110][2];
ll g[110][110][2];
ll tmp[110][110][2];
int e[110][110];
void update(int f, int s) ///背包二进制优化
{
    for(int k = 1; k <= n; k++)
    {
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                A[s][i][j][0] += A[f][i][k][0] * A[f][k][j][0] % mod; ///2^f步都没有附魔
                A[s][i][j][0] += A[f][i][k][1] * A[f][k][j][1] % mod; ///都附魔了
                A[s][i][j][1] += A[f][i][k][0] * A[f][k][j][1] % mod;
                A[s][i][j][1] += A[f][i][k][1] * A[f][k][j][0] % mod;
                A[s][i][j][0] %= mod; //都要取模
                A[s][i][j][1] %= mod;
            }
        }
    }
}
void add(int f)
{
    memset(tmp, 0, sizeof tmp);
    for(int k = 1; k <= n; k++)
    {
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                tmp[i][j][0] += g[i][k][0] * A[f][k][j][0] % mod;
                tmp[i][j][0] += g[i][k][1] * A[f][k][j][1] % mod;
                tmp[i][j][1] += g[i][k][1] * A[f][k][j][0] % mod;
                tmp[i][j][1] += g[i][k][0] * A[f][k][j][1] % mod;
                tmp[i][j][0] %= mod;
                tmp[i][j][1] %= mod;
            }
        }
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            for(int k = 0; k <= 1; k++)
            {
                g[i][j][k] = tmp[i][j][k];
            }
        }
    }
}

void solve()
{
    int m, k;
    scanf("%d%d%d", &n, &m, &k);
    memset(e, -1, sizeof e);
    memset(A, 0, sizeof A);
    memset(g, 0, sizeof g);
    for(int i = 1; i <= m; i++)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        e[x][y] = z; ///建桥
        e[y][x] = z; //是否是附魔桥
    }
    for(int i = 1; i <= n; i++)
    {
        int sum = 0;
        for(int j = 1; j <= n; j++)
        {
            sum += (e[i][j] >= 0); ///是否存在这座桥
        }
        for(int j = 1; j <= n; j++)
        {
            if(e[i][j] < 0) continue; ///不存在这座桥
            A[0][i][j][e[i][j]] = qpow(sum, mod - 2);
        }
    }

    for(int i = 1; i <= n; i++) ///一步 初始化答案
    {
        for(int j = 1; j <= n; j++)
        {
            g[i][j][0] = A[0][i][j][0];
            g[i][j][1] = A[0][i][j][1];
        }
    }
    for(int i = 1; (1 << i) <= k; i++)
        update(i - 1, i);
    k--;
    for(int i = 20; i >= 0; i--)
    {
        if(k >= (1 << i))
        {
            add(i);
            k -= (1 << i);
        }
    }
    printf("%lld\n", g[1][n][1]);
}