20211020 航行 sail

怎么也没想到我会来做期望的题，还想写题解。。

其实就是把别人的题解用我自己也能看懂的语言抄一遍

Description

一条线有 \(n\) 个点，初始速度为 \(0\) ，假设向右为正速度，对于每个点 \(i\) ，有 \(\frac{p_i}{100}\) 的几率刮西风，速度加一，反之刮东风，速度减一，如果每次变完速度为 \(v\) ，此时从当前点 \(u\) 转移到 \(u + v\) ，当坐标不在 \([1, n]\) 的时候就立即停止。

求从 \([1, n]\) 的每个点作为起始点，求期望走的次数，走不出去的话输出 \(-1\) 。

Analysis

啊啊啊，看到这种题就很烦，但还是要做呀。。

老思路，想一想一共会有哪些状态，对于每个点，速度能从 \(0\) 到 \(n\) ，在大也不可能了，不然速度为 \(n\) 的时候早就一下走出去了。

那么先标记好： \(f_{i, j}\) 表示出现状态为在第 \(i\) 个点，速度为 \(j\) 时的概率。

Solution

Part1（ \(O(n^6)\) ）

继续接着老思路走，我们要想对于每个状态，有哪些其他状态可以到达。

其实应该很显然，分成刮西风和刮东风两种情况。

那么对于任意一个 \(f_{i, j}\) ，我们就能确定两个速度，那么从左右两边过来的话，每个速度对应两个点，一共就能至多从四个状态转移过来。

假如走出去了怎么办，不管他，但是要标记这个点这个速度能够走出去，否则根本算不了，这个后面说。

那么这样的话我们就得到了 \(n^2\) 个关系。

然后就很自然的想到了高消，那么对于每次从每个点出发，\(f_{i, 0}\) 概率为 \(1\) ，解 \(n\) 次方程，总共是 \(O(n^7)\) 的。

前两天的考试里面有一道题就出现了类似的情况，要解 \(n\) 次方程，但观察整个高消的过程，如果只是常熟的改变，并不影响高消顺序，所以可以把整个 n 组常熟压到一起解。

所以时间复杂度就是 \(O(n^6)\) 了。

到这里，其实思路都是很自然的顺下来，目前还没有新思路，那先来补坑，怎么判 \(-1\) 。

想到如果是 \(-1\) ，一定就是指没有一个能到达的状态能走出去，又因为概率问题，所以每个状态必然能到达至少一个至多两个其他的状态。

所以这就肯定是围成了一个环，当然不止着一种情况，如果没有答案，还有可能是一个环能够走向一个“死环”（就指没有出边的环）。

（心里话：一开始我在想，为什么是能够而不是只能，后来我发现，每个关系指向的状态都会对出发状态产生贡献。如果贡献算不了，是 \(-1\) ，那么这里的贡献就缺失了，自然也算不了出发状态的贡献了。）

这样看的话，我们可以先把每个状态和能到达的状态连边，就可以考虑缩点，然后拓扑序去排掉 \(-1\) 的状态，剩下的都是合法的，也就可以继续算了。

Part2（ \(O(n^{4.5})\) ）

虽说速度我们开到了 \(n\) ，但是每次走的话，速度至多减一，其实只要最后到边界的时候，速度为 \(1\) ，就能走出去。

这就相当于对于一个速度，速度每次减一，到边界的时候速度为一，一共至少走了 \(n\) 步就行（注意不是 \(n\) 次。。），那么这个上限能算，就是 \(\sqrt{2n}\) 。

于是状态数就减少到 \(O(n^{1.5})\) ，时间复杂度就来到了 \(O(n^{4.5})\) ， \(-1\) 的情况同上。

Part3（ \(O(n^3)\) ）

其实所有式子合在一起看上去非常“不错”，因为几乎全是 \(0\) ，即便是 Part2 无用状态太多，但又不能去掉，非常的烦。

那么我们是不是能做到只保留 \(n\) 个式子呢？？

那要看我们怎么把一些用处不大但又必须要有的状态提前合并到一块了。

最直接的想法就是只保留 \(f_{i, 0}\) ，那么这样的话，本身我们只确定每个状态与其他状态的直接贡献，我们要转换到确定每个状态到所有状态的贡献，无论是直接的，还是间接的。

形象地理解，就是我们知道一张图所有边的样子，现在我们要变成要知道整张图的样子。

想到的肯定是 DP 预处理，但很快我们又会发现我们前面设的 \(f_{i, j}\) 怎么算都有后效性，预处理是不太可能了。

尝试添加一维： \(g_{i, j, k}\) 表示 i 个点从第 j 个点在速度为 k 的时候（经过一系列转移）走来的概率。

这样融合了状态在里面的 DP ，我们可以尝试每个点分开求，从 \(g_{i, i, 0}\) 开始，向两边扩散。

大概意思就是对于一个点 \(i\) ，有这么四种情况：

\[\forall_{k\in [1, \sqrt{2n}]} \forall_{j\in [k+1, i-1]} \ g_{i, j - (k + 1), k + 1} += g_{i, j, k} \cdot \frac{p_i}{100} \]

\[\forall_{k\in [1, \sqrt{2n}]} \forall_{j\in [k-1, i-1]} \ g_{i, j - (k - 1), k - 1} += g_{i, j, k} \cdot \frac{100 - p_i}{100} \]

\[\forall_{k\in [1, \sqrt{2n}]} \forall_{j\in [i+1, n-(k+1)]} \ g_{i, j + (k + 1), k + 1} += g_{i, j, k} \cdot \frac{100 - p_i}{100} \]

\[\forall_{k\in [1, \sqrt{2n}]} \forall_{j\in [i+1, n-(k-1)]} \ g_{i, j + (k - 1), k - 1} += g_{i, j, k} \cdot \frac{p_i}{100} \]

这里是时间 \(O(n^{2.5})\) 的，挺好，可以做。

至于后面两个为什么概率看上去像是对应错了，其实是速度表示的时候负的也表示成了正的而已。

（心里话：乱扯，速度正负怎么可以表示成同一个呢？？那不就会重合，不就错了吗？？欸不对，速度为正的时候， \(i\) 一定大于 \(j\) ，速度为负的时候， \(i\) 一定小于 \(j\) ，怎么会冲突呢。关键还方便一点，不用判谁大谁小来决定速度大小就能用）

这样下来，对于任意两个点，如果存在 \(g_{i, j, 0}\) ，不就相当于是前面提到的只保留 \(f_{j, 0}\) 的状态嘛，甚至连具体哪个点都定了，可以直接上高消了。

判 \(-1\) 的方法还是和上面一样，时间复杂度总共 \(O(n^3)\) 。

但其实还没完，因为我们并不知道求解完要怎么算，我们解出来了每个点速度为零时走到其他点的期望次数，在乘上对应点被走到的概率，才是答案。

那在之前算完 \(g_{i, j, k}\) 之后就可以把 \(i\) 点被走到的概率统计好。

整个题到这里就算是做完了，具体小细节看看代码就能懂了！

Code

主要是感觉 std 的代码有点毒瘤，我就把我的代码放出来吧。

/*

*/
#include 
using namespace std;
typedef long long ll;
const int N = 1e3 + 10, M = 42;
const ll mod = 998244353, inv = 828542813;
int n, fst[N], tot, col[N], cnt, du[N], ok[N];
int dfn[N], low[N], tim, sta[N], top;
bool sig[N][N];
ll f[N][N][M], all[N], gs[N][N + N];
struct mdzz {ll p1, p2;} a[N];
struct edge {int nxt, to;} e[N * N];
vector g[N];
const int Mxdt = 100000;
inline char gc() {
	static char buf[Mxdt], *p1 = buf, *p2 = buf;
	return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, Mxdt, stdin), p1 == p2) ? EOF : *p1++;
}
inline ll read() {
	ll s = 0, w = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {if (ch == '-') w = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {s = (s << 3) + (s << 1) + ch - '0'; ch = getchar();}
	return s * w;
}
inline void add(int u, int v) {
	e[++tot] = (edge) {fst[u], v};
	fst[u]= tot;
}
inline ll ksm(ll a, ll b) {
	ll tmp = 1;
	while (b) {
		if (b & 1) tmp = tmp * a % mod;
		a = a * a % mod; b >>= 1;
	}
	return tmp;
}
inline void Gauss_Jordan(int n, int p) {
	for (int i = 1; i <= n; ++i) {
		int now = i;
		for (int j = i; j <= n; ++j) {
			if (abs(gs[j][i]) > abs(gs[now][i])) now = j;
		}
		for (int j = 1; j <= p; ++j) {
			swap(gs[i][j], gs[now][j]);
		}
		/*if (!gs[i][i]) {
			printf("No Solution\n");
			return ;
		}*/
		ll invv = ksm(gs[i][i], mod - 2);
		for (int j = p; j >= i; --j) gs[i][j] = gs[i][j] * invv % mod;
		for (int j = 1; j <= n; ++j) if (j != i) {
			for (int k = p; k >= i; --k) {
				gs[j][k] = (gs[j][k] - (gs[j][i] * gs[i][k] % mod) + mod) % mod;
			}
		}
	}
	for (int i = 1; i <= n; ++i) {
		int invv = ksm(gs[i][i], mod - 2);
		for (int j = n + 1; j <= p; ++j){
			gs[i][j] = gs[i][j] * invv % mod;
		}
	}
}
inline void tarjan(int u) {
	dfn[u] = low[u] = ++tim; sta[++top] = u;
	for (int i = fst[u]; i; i = e[i].nxt) {
		int v = e[i].to;
		if (!dfn[v]) {
			tarjan(v);
			low[u] = min(low[u], low[v]);
		}
		else if (!col[v]) {
			low[u] = min(low[u], dfn[v]);
		}
	}
	if (dfn[u] == low[u]) {
		++cnt;
		while (sta[top] != u) {
			col[sta[top]] = cnt; --top;
		}
		col[u] = cnt; --top;
	}
}
inline void toposort() {
	queue q;
	for (int i = 1; i <= cnt; ++i) {
		if (!du[i]) {
			ok[i] = -1;
			q.push(i);
		}
	}
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (int i = 0; i < (int)g[u].size(); ++i) {
			int v = g[u][i];
			if (--du[v] == 0) {
				if (ok[u] == -1) ok[v] = -1;
				q.push(v);
			}
		}
	}
}
int main() {
//	freopen("sail.in", "r", stdin);
//	freopen("sail.out", "w", stdout);
	n = read();
	if (n == 1) {
		printf("1\n");
		return 0;
	}
	for (int i = 1; i <= n; ++i) {
		a[i].p1 = read() * inv %mod;
		a[i].p2 = (1 - a[i].p1 + mod) % mod;
	}
	for (int i = 1; i <= n; ++i) {
		int sigg = 0;//看能不能跑出去
		//先初始化
		if (a[i].p1 && i != 1) f[i][i - 1][1] = a[i].p1;
		if (a[i].p1 && i == 1) sigg = 1;
		if (a[i].p2 && i != n) f[i][i + 1][1] = a[i].p2;
		if (a[i].p2 && i == n) sigg = 1;
		//对于每个点和一个速度，算当前状态的贡献
		for (int j = i - 1; j >= 1; --j) {
			for (int k = 1; k <= 32; ++k) {
				if (!f[i][j][k]) continue;
				if (a[j].p1 && j > k + 1) (f[i][j - (k + 1)][k + 1] += f[i][j][k] * a[j].p1 % mod) %= mod;
				if (a[j].p1 && j <= k + 1) sigg = 1;
				if (a[j].p2 && j > k - 1) (f[i][j - (k - 1)][k - 1] += f[i][j][k] * a[j].p2 % mod) %= mod;
				if (a[j].p2 && j <= k - 1) sigg = 1;
			}
			//速度为零时两点是否有概率到达
			if (f[i][j][0]) add(i, j);
		}
		for (int j = i + 1; j <= n; ++j) {
			for (int k = 1; k <= 32; ++k) {
				if (!f[i][j][k]) continue;
				if (a[j].p2 && j + k + 1 <= n) (f[i][j + (k + 1)][k + 1] += f[i][j][k] * a[j].p2 % mod) %= mod;
				if (a[j].p2 && j + k + 1 > n) sigg = 1;
				if (a[j].p1 && j + k - 1 <= n) (f[i][j + (k - 1)][k - 1] += f[i][j][k] * a[j].p1 % mod) %= mod;
				if (a[j].p1 && j + k - 1 > n) sigg = 1;
			}
			//速度为零时两点是否有概率到达
			if (f[i][j][0]) add(i, j);
		}
		if (sigg) add(i, 0);
		all[i] = 1;
		for (int j = 1; j <= n; ++j) if (i != j) {
			for (int k = 1; k <= 32; ++k) {
				all[i] += f[i][j][k];
			}
		}
		all[i] %= mod;
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			if (i == j) gs[i][i] = 1;
			else gs[i][j] = (mod - f[j][i][0]) % mod;
		}
		gs[i][i + n] = 1;//从这里出发
	}
	for (int i = 1; i <= n; ++i) {
		if (!dfn[i]) {
			top = 0; tarjan(i);
		}
	}
	for (int u = 1; u <= n; ++u) {
		for (int i = fst[u]; i; i = e[i].nxt) {
			int v = e[i].to;
			if (col[u] != col[v]) {
				g[col[u]].push_back(col[v]);
				if (!sig[col[u]][col[v]]) ++du[col[u]];
				sig[col[u]][col[v]] = 1;
			}
		}
	}
	toposort();
	for (int i = 1; i <= n; ++i) {
		if (ok[col[i]] == -1) {
			for (int j = 1; j <= n; ++j) {
				gs[i][j] = gs[j][i] = 0;
			}
		}
	}
	Gauss_Jordan(n, n + n);
	for (int i = 1; i <= n; ++i) {
		if (ok[col[i]] == -1) {
			printf("-1 "); continue;
		}
		ll ans = 0;
		for (int j = 1; j <= n; ++j) if (ok[col[j]] != -1) {
			ans += (gs[j][i + n] * all[j] % mod);
		}
		ans %= mod;
		printf("%lld ", ans);
	}
	return 0;
}