# HDU7016 Random Walk 2

2021-08-08 00:30:49 mrclr

Portal

What a pity , At the end of the game 10 Minutes pushed out , however 10 You can't finish Gaussian elimination in minutes .

There are many ideas for this question , A kind of problem solving , And another kind of big man in our team , And my own kind of . But I don't quite understand the other two ideas , So I can only record my thoughts here .

I did this problem according to the random walk model in the figure .

Let's start with $$1$$ Number point . Make $$E(u)$$ Said go $$u$$, And the probability of going on ,$$f(u)$$ Said go $$u$$, And stop at $$u$$ Probability . Being able to go on means that you can't be in $$u$$, Stopping means that the last moment must be $$u$$.

Then you can list the relationship ：

$$F(u)=E(u) * P(u,u) + P(1,1)*(u == 1)$$,
$$E(u)=\sum\limits_{v = 1,v \neq u} ^ {n} E(v) * P(v, u) + P(1,u) * (u \neq 1)$$.

Notice the following constant term , Because at first $$1$$ Number point , So there is $$P(1,1)$$ The probability of stopping , Yes $$P(1,u)$$ The probability of going to another point .（ Just because of these constant terms, I don't understand , Pushed wrong and gave up ）
$$E(u)$$ The relationship between them can be solved by Gaussian elimination , You can get it by substituting in $$F(u)$$ 了 .

Above is the starting point in $$1$$ The situation of , So for the starting point $$x$$ The situation of , We find that the coefficient matrix is the same , Only the rightmost column of the augmented matrix is different , Therefore, the augmented matrix can be written as $$n+n$$ Column ,$$n$$ Simultaneous solutions of two equations . So time complexity is $$O(n * n * 2n)$$.

Of course , You can also list the matrix equations and find the inverse , The effect is the same .

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<queue>
#include<assert.h>
#include<ctime>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
#define forE(i, x, y) for(int i = head[x], y; ~i && (y = e[i].to); i = e[i].nxt)
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const ll mod = 998244353;
const int maxn = 302;
{
ll ans = 0;
char ch = getchar(), las = ' ';
while(!isdigit(ch)) las = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(las == '-') ans = -ans;
return ans;
}
In void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}

In ll ADD(ll a, ll b) {return a + b < mod ? a + b : a + b - mod;}
In ll quickpow(ll a, ll b)
{
ll ret = 1;
for(; b; b >>= 1, a = a * a % mod)
if(b & 1) ret = ret * a % mod;
return ret;
}

int n, m;
ll p[maxn][maxn];

ll f[maxn][maxn << 1];
In void Gauss()
{
for(int i = 1; i <= n; ++i)
{
int pos = i;
while(pos <= n && !f[pos][i]) ++pos;
if(pos > n) continue;
if(pos > i) swap(f[i], f[pos]);
ll inv = quickpow(f[i][i], mod - 2);
for(int j = i; j <= m; ++j) f[i][j] = f[i][j] * inv % mod;
for(int j = i + 1; j <= n; ++j)
{
ll tp = f[j][i];
for(int k = i; k <= m; ++k) f[j][k] = ADD(f[j][k], mod - tp * f[i][k] % mod);
}
}
for(int i = n; i; --i)
for(int j = i - 1; j; --j)
for(int k = n + 1; k <= m; ++k)
f[j][k] = ADD(f[j][k], mod - f[j][i] * f[i][k] % mod);
}
In void solve()
{
Mem(f, 0); m = n + n;
for(int i = 1; i <= n; ++i)
{
ll sum = 0;
for(int j = 1; j <= n; ++j) sum += p[i][j];
sum = quickpow(sum, mod - 2);
for(int j = 1; j <= n; ++j) p[i][j] = p[i][j] * sum % mod;
}
for(int i = 1; i <= n; ++i)
{
f[i][i] = 1;
for(int j = 1; j <= n; ++j)
if(i ^ j)
{
f[i][j] = mod - p[j][i];
f[j][n + i] = ADD(f[j][n + i], p[i][j]);
}
}
Gauss();
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
{
write(ADD(f[j][n + i] * p[j][j] % mod, (i == j) * p[j][j]));
j == n ? enter : space;
}
}

int main()
{
while(T--)
{
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j) p[i][j] = read();
solve();
}
return 0;
}


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.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.


https://chowdera.com/2021/08/20210808003020385a.html