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]);
}