题目描述
https://acm.hdu.edu.cn/showproblem.php?pid=7016
简要题意：给出一张完全图以及从每个点到达另一个点的概率 $p_{i,j}$，另外每个点 $i$ 都有 $p_{i,i}$ 的概率在点 $i$ 停下，对于所有 $(i,j)$，求从 $i$ 出发停在 $j$ 的概率
$n\le 300$
Solution
首先我们考虑构造矩阵 $A$，满足 $A_{i,j}=p_{i,j},A_{i,i}=0$，那么 $A^1+A^2+\cdots A^{\infty}=B$，$B_{i,j}$ 即为 $i$ 走了若干步到 $j$ 且中间没有停下来的概率，那么我们要求的答案就是 $B_{i,j}\times p_{i,i}$
我们考虑如何求 $B$，注意到 $A$ 为幂零矩阵，所以 $A^{\infty}=0$，我们直接套用等比数列求和公式得到 $B=\frac{I}{I-A}$
注意到因为 $A$ 为幂零矩阵，所以 $I-A$ 一定有逆矩阵
时间复杂度 $O(n^3)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| #include <iostream>
#define maxn 310
#define ll long long
using namespace std;
const int p = 998244353;
ll pow_mod(ll x, ll n) {
ll s = 1;
for (; n; n >>= 1, x = x * x % p)
if (n & 1) s = s * x % p;
return s;
}
int n;
ll P[maxn];
ll g[maxn][2 * maxn];
void Gauss() {
for (int i = 1; i <= n; ++i) g[i][n + i] = 1;
for (int i = 1; i <= n; ++i) {
int pos = -1;
for (int j = i; j <= n; ++j) if (g[j][i]) pos = j;
swap(g[pos], g[i]); ll inv = pow_mod(g[i][i], p - 2);
for (int j = i; j <= 2 * n; ++j) g[i][j] = g[i][j] * inv % p;
for (int j = 1; j <= n; ++j) {
if (j == i) continue;
for (int k = i + 1; k <= 2 * n; ++k)
g[j][k] = (g[j][k] - g[j][i] * g[i][k]) % p;
g[j][i] = 0;
}
}
}
void work() {
cin >> n;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= 2 * n; ++j) g[i][j] = 0;
for (int i = 1; i <= n; ++i) {
ll sum = 0;
for (int j = 1; j <= n; ++j) cin >> g[i][j], sum += g[i][j];
for (int j = 1; j <= n; ++j) g[i][j] = g[i][j] * pow_mod(sum, p - 2) % p;
}
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
if (i == j) P[i] = g[i][i], g[i][i] = 1;
else g[i][j] = -g[i][j];
Gauss();
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j) {
ll ans = g[i][j + n] * P[j] % p;
cout << (ans + p) % p << " \n"[j == n];
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int T; cin >> T;
while (T--) work();
return 0;
}
|