Loj 3080 国际象棋

Posted on | Views:

主元法求解网格图上的随机游走问题.

朴素的高斯消元是 $O((nm)^3)$ 的,无法通过.

考虑主元法,将前 $2$ 行,第 $1$ 列的共计 $2m+n-2$ 个变量作为主元,尝试将其他变量用主元表示,并解出主元的值.

从上到下,从左到右依次考虑每个位置的方程,可以发现其中只有 $x_{i+2,j+1}$ 还没有被主元表示.

根据方程,若 $(i+2,j+1)$ 在棋盘内,就可以将 $x_{i+2,j+1}$ 也用主元表示,若不在棋盘内,则得到了一个关于主元的方程.

最后恰好能得到 $2m+n-2$ 个关于主元的线性方程,用高斯消元求解主元的值即可,时间复杂度 $O((n+m)^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
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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
//%std
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define y1 ysgh
inline int read()
{
	int out = 0, fh = 1;
	char jp = getchar();
	while ((jp > '9' || jp < '0') && jp != '-') jp = getchar();
	if (jp == '-')
		fh = -1, jp = getchar();
	while (jp >= '0' && jp <= '9') out = out * 10 + jp - '0', jp = getchar();
	return out * fh;
}
void print(int x)
{
	if (x >= 10)
		print(x / 10);
	putchar('0' + x % 10);
}
void write(int x, char c)
{
	if (x < 0)
		putchar('-'), x = -x;
	print(x);
	putchar(c);
}
namespace Module
{
	const int P = 998244353;
	int add(int a, int b)
	{
		return a + b >= P ? a + b - P : a + b;
	}
	void inc(int &a, int b)
	{
		a = add(a, b);
	}
	int mul(int a, int b)
	{
		return 1LL * a * b % P;
	}
	int fpow(int a, int b)
	{
		int res = 1;
		while (b)
		{
			if (b & 1)
				res = mul(res, a);
			a = mul(a, a);
			b >>= 1;
		}
		return res;
	}
}
using namespace Module;
const int N = 200 + 10;
int dx[8] = { -2, -1, 1, 2, 2, 1, -1, -2 }, dy[8] = { -1, -2, -2, -1, 1, 2, 2, 1 };
int p[8], inv[8], n, m, swaped = 0, k, coef[N][N][3 * N];
int a[3 * N][3 * N], val[3 * N], tmp[3 * N], t = 0;
bool in(int x, int y)
{
	return 1 <= x && x <= n && 1 <= y && y <= m;
}
void InitPivot()
{
	k = 2 * m + n - 2;
	val[0] = 1;
	for (int j = 1; j <= m; ++j) coef[1][j][j] = 1, coef[2][j][j + m] = 1;
	for (int i = 3; i <= n; ++i) coef[i][1][2 * m + i - 2] = 1;
}
void BuildEquations()
{
	for (int x = 1; x <= n; ++x)
		for (int y = 1; y <= m; ++y)
		{
			for (int i = 0; i <= k; ++i) tmp[i] = add(0, P - coef[x][y][i]);
			inc(tmp[0], 1);
			for (int d = 0; d < 8; ++d)
				if (d != 4)
				{
					int cx = x + dx[d], cy = y + dy[d];
					if (in(cx, cy))
						for (int i = 0; i <= k; ++i) 
							inc(tmp[i], mul(p[d], coef[cx][cy][i]));
				}
			if (x + 2 <= n && y + 1 <= m)
			{
				for (int i = 0; i <= k; ++i) 
					coef[x + 2][y + 1][i] = mul(inv[4], P - tmp[i]);
			}
			else
			{
				++t;
				for (int i = 0; i <= k; ++i) a[t][i] = tmp[i];
				a[t][0] = add(0, P - a[t][0]);
			}
		}
	assert(t == k);
}
void Gauss()
{
	for (int i = 1; i <= k; ++i)
	{
		for (int j = i; j <= k; ++j)
			if (a[j][i])
			{
				if (i != j)
					for (int l = 0; l <= k; ++l) swap(a[j][l], a[i][l]);
				break;
			}
		int f = fpow(a[i][i], P - 2);
		for (int j = 1; j <= k; ++j)
			if (i != j && a[j][i])
			{
				int g = mul(f, P - a[j][i]);
				for (int l = 0; l <= k; ++l) inc(a[j][l], mul(a[i][l], g));
			}
	}
	for (int i = 1; i <= k; ++i) val[i] = mul(a[i][0], fpow(a[i][i], P - 2));
}
int main()
{
	n = read(), m = read();
	int sum = 0;
	for (int i = 0; i < 8; ++i) inc(sum, p[i] = read());
	for (int i = 0; i < 8; ++i) 
	{
		p[i] = mul(p[i], fpow(sum, P - 2));
		inv[i] = fpow(p[i], P - 2);
	}
	InitPivot();
	BuildEquations();
	Gauss();
	int q = read();
	while (q--)
	{
		int x = read(), y = read();
		int s = 0;
		for (int i = 0; i <= k; ++i) inc(s, mul(val[i], coef[x][y][i]));
		write(s, '\n');
	}
	return 0;
}