1007D. 航行（高消之把可以递推的丢到外面处理）

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/142742037

http://cplusoj.com/d/senior/p/SS241007D

前面64分显然，搜个状态，然后转移就行，这不是重点。

考虑我们现在高消的状态数太大，而我们实际上需要的只有 (x,0)(x,0) 的状态，那它们之间能不能提前把关系推出来呢？

假如当前速度是0，我们想知道到下一次速度是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
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
 #define debag(...) fprintf(stderr, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
 #define debag(...) void(0)
#endif
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//#define M
#define mo 998244353
#define N 510
int pw(int a, int b) {
	int ans = 1; 
	while(b) {
		if(b & 1) ans *= a; 
		a *= a; b >>= 1; 
		ans %= mo; a %= mo; 
	}
	return ans; 
}
int pw(int a) { return pw(a, mo - 2); }
inline void Mod(int &a) { if(a >= mo || a <= -mo) a %= mo; if(a < 0) a += mo; }
inline void Add(int &a, int b) { a += b; Mod(a); }
inline void Mul(int &a, int b) { Mod(b); a *= b; Mod(a); } 
int n, m, i, j, k, T, tot;
map<pair<int, int>, int>vis; 
vector<pair<int, int> >G; 
int a[N][N], p[N], fm, Ans[N], ans[N]; 

void print() {
	int i, j; 
	for(i = 1; i <= tot; ++i, debug("\n"))
		for(j = 1; j <= tot + 1; ++j) debug("%lld ", a[i][j]); 
	debug("--------------------------\n"); 
}

void Gauss(int n) {
//	print(); 
	for(i = 1; i <= n; ++i) {
		for(j = i, k = 0; j <= n; ++j) if(a[j][i]) k = j; 
		if(!k) continue; 
		for(j = 1; j <= n + 1; ++j) swap(a[k][j], a[i][j]); 
		for(j = 1, k = pw(a[i][i]); j <= n + 1; ++j) Mul(a[i][j], k); 
//		print(); 
		for(j = 1; j <= n; ++j) if(j != i && a[j][i]) {
			int x = -a[j][i]; 
			for(k = 1; k <= n + 1; ++k) Add(a[j][k], x * a[i][k]); 
		}
	}
	for(i = 1; i <= n; ++i) {
		if(!Ans[i]) continue; 
		if(!a[i][i] || !a[i][n + 1]) { ans[Ans[i]] = -1;  continue; }
		for(j = 1; j <= n; ++j) if(j != i && a[i][j]) break; 
		if(j <= n) { ans[Ans[i]] = -1; continue; }
		ans[Ans[i]] = a[i][n + 1]; 
	}
}

struct node {
	int p, c; 
	void add(node F, int P) {
		Add(p, F.p * P); Add(c, (F.c + F.p) * P % mo); 
	}
}f[N][101];

signed main()
{
	  freopen("sail.in", "r", stdin);
	  freopen("sail.out", "w", stdout);
//	srand(time(NULL));
//	T = read();
//	while(T--) {
//
//	}
	n = read(); fm = pw(100); 
	for(i = 1; i <= n; ++i) {
		k = read(); p[i] = k * fm % mo; Ans[i] = i; 
	}
	for(i = 1; i <= n; ++i) {
		memset(f, 0, sizeof(f)); 
		f[i + 1][1] = {1 - p[i], 1 - p[i]}; f[i - 1][1] = {p[i], p[i]}; 
		for(j = i + 1; j <= n; ++j)
			for(k = 1; k <= 100; ++k) {
				f[min(n + 1, j + k - 1)][k - 1].add(f[j][k], p[j]); 
				f[min(n + 1, j + k + 1)][k + 1].add(f[j][k], 1 - p[j]); 
			}
		for(j = i - 1; j >= 1; --j) 
			for(k = 1; k <= 100; ++k)  {
				f[max(0ll, j - (k - 1))][k - 1].add(f[j][k], 1 - p[j]); 
				f[max(0ll, j - (k + 1))][k + 1].add(f[j][k], p[j]); 
			}
		for(j = 1; j <= n; ++j) 
			if(i != j) a[i][j] = -f[j][0].p, Add(a[i][n + 1], f[j][0].c), debug("%lld\n", f[j][0].c);
		for(j = 0; j <= 100; ++j) Add(a[i][n + 1], f[0][j].c + f[n + 1][j].c), debug("%lld %lld\n", f[0][j].c, f[n + 1][j].c); 
		a[i][i] = 1; 
	}
	tot = n; 
//	debug("== %lld %lld\n", pw(2), pw(4)); 
//	print(); 
	Gauss(tot); 
	for(i = 1; i <= n; ++i) printf("%lld ", ans[i]); 
	return 0;
}