扫雷

题意:

有 \(n \times m\) 的个格子，总共 \(W\) 个雷，钦定 \(K\) 个雷，一个格子的价值是相邻 \(8\) 个格子内雷的个数，并且这个格子不是雷。

一种可能的局面的价值是所有格子的价值和，求所有可能局面的期望和方差。

计数:

不妨设可选的空格 \(T = n \times m - W\), 未确定的雷的个数 \(W = W - K\)。

由于期望的线性性，所有局面的期望即为每个格子的期望，即 $$E(x) = \sum E(x_{i,j})$$

这部分需要考虑：

1. 这个点没钦定雷。

2. 知道周围8个格子内，能放雷的空格个数 \(i\), 已经钦定雷的个数 \(p\)。

3. 对满足上述 \(i, p\) 的格子计数。

那么对于每个 \(i, p\) 有 \(\text{cnt}_{i,j}\) 个格子，对期望的贡献是

\[(\sum_{j = 0}^{i} \binom{i}{j}\binom{T - j - 1}{W - p - j} \times (p + j))\times \text{cnt}_{i,j} \]

这个组合意义是：枚举放的雷的个数 \(j\), 选出放的位置，并在剩下\(T - j - 1\)空位内随便放剩下的 \(W - p - j\) 个雷，贡献了 \((p + j)\) 的价值。

方差

\[D = E(x^2) - E^2(x) \]

考虑如何计算 \(E(x^2)\):

\[E(x^2) = \sum E(x_{i,j}^2) + \sum_{(i,j) \neq (x,y)} E(x_{i,j}x_{x,y}) \]

对于 \(\sum E(x_{i,j}^2)\) 和上面计算期望的方式类似。

考虑如何计算 \(\sum_{(u \neq v} E(x_ux_v)\)，这部分需要考虑:

1. 两点都没钦定雷。

2. 知道相邻八个格子内, \(u\) 坐标周围空格的个数 \(i\), \(v\) 周围空格 \(j\), \(u\),\(v\) 公共部分的空格 \(k\),前两个不包含公共部分, \(u\) 周围钦定雷的个数 \(p\), \(v\) 周围钦定雷的个数 \(q\).

3. 统计满足 \((i,j,k,p,q)\) 的格子的个数 \(g_{i,j,k,p,q}\)。

枚举 \((i,j,k,p,q)\) 和对 \(u\)周围的空格、\(v\) 周围的空格、公共部分的空格分别放几个雷。

假设分别选了 \(P, Q, K\) 个。

这部分贡献是:

\[(\sum_{P = 0}^{i}\sum_{Q = 0}^{j}\sum_{K = 0}^{k}\binom{i}{P}\binom{j}{Q}\binom{k}{K}\binom{T - i - j - k - 2}{W - P - Q - K} \times (P + p + r) \times (Q + q + r))\times g_{i,j,k,p,q} \]

组合意义是：挑两个格子挑 \(P, Q\) 和 公共部分挑 \(K\) 个雷，并在剩下的格子和剩下的雷里选，对两个格子的价值相乘。

就能计算出方差了。

代码

#include

using namespace std;

using ll = long long;
const int MAXN = 400010;
const int INF = 0x7fffffff;
const int mod = 998244353;

template 
void Read(T &x) {
	x = 0; T f = 1; char a = getchar();
	for(; a < '0' || '9' < a; a = getchar()) if (a == '-') f = -f;
	for(; '0' <= a && a <= '9'; a = getchar()) x = (x * 10) + (a ^ 48);
	x *= f;
}

int add(int a, int b) {
	int c = a + b;
	if (c >= mod) c -= mod;
	if (c < 0) c += mod;
	return c;
}
int mul(int a, int b) {
	return 1ll * a * b % mod;
}
int qpow(int a, int b) {
	int sum(1);
	while(b) {
		if (b & 1) sum = mul(sum, a);
		a = mul(a, a);
		b >>= 1;
	}
	return sum; 
}
int f[MAXN], ifa[MAXN]; 
void pre(int n) {
	f[0] = 1; 
	for (int i = 1; i <= n; i ++)
		f[i] = mul(f[i - 1], i);
	ifa[n] = qpow(f[n], mod - 2);
	for (int i = n - 1; i >= 0; i --)
		ifa[i] = mul(ifa[i + 1], i + 1);
}
int C(int n, int m) {
	if (n < m || m < 0 || n < 0) return 0; 
	return mul(f[n], mul(ifa[m], ifa[n - m])); 
}

int n, m, W, K; 
const int dx[] = {-1, -1, -1,  0, 0,  1, 1, 1, -2, -2, -2, -2, -2, -1, -1, 0,  0,  1, 1,  2,  2, 2, 2, 2};
const int dy[] = {-1,  0,  1, -1, 1, -1, 0, 1, -2, -1,  0,  1,  2, -2,  2, -2, 2, -2, 2, -2, -1, 0, 1, 2}; 

int A[MAXN], *a[MAXN], B[MAXN], *b[MAXN], _C[MAXN], *c[MAXN];
int cnt[20][20], g[20][20][20][20][20];  

bool valid(int x, int y) {
	return x >= 1 && y >= 1 && x <= n && y <= m; 
} 


signed main() {
//	freopen("A4.in", "r", stdin); 
//	freopen("out.out", "w", stdout);
	Read(n); Read(m); Read(W); Read(K); 
	pre(n * m); 
	a[1] = A, b[1] = B, c[1] = _C; 
	for (int i = 2; i <= n; i ++) 
		a[i] = a[i - 1] + m, b[i] = b[i - 1] + m, c[i] = c[i - 1] + m;
	int S = n * m, T = S - K; W -= K; 
	for (int i = 1; i <= K; i ++) {
		int x, y;
		Read(x); Read(y);
		a[x][y] = 1; 
	} 
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= m; j ++)
			if (!a[i][j]) {
				for (int k = 0; k < 8; k ++) {
					int x = dx[k] + i, y = dy[k] + j;
					if (!valid(x, y)) continue;
					if (a[x][y]) c[i][j] ++; 
					else b[i][j] ++; 
				}
				cnt[b[i][j]][c[i][j]] ++; 
			}
	
	for (int i = 0; i <= 8; i ++)
		for (int j = 0; j <= 8; j ++)
			for (int p = 0; p <= 8 - i; p ++)
				for (int q = 0; q <= 8 - j; q ++)	
					if (i == j && p == q) g[i][j][0][p][q] = mul(cnt[i][p], add(cnt[i][p], -1));
					else g[i][j][0][p][q] = mul(cnt[i][p], cnt[j][q]);
	
	for (int _i = 1; _i <= n; _i ++)
		for (int _j = 1; _j <= m; _j ++)	
			if (!a[_i][_j]) {
				for (int _k = 0; _k < 24; _k ++) {
					int x = dx[_k] + _i, y = dy[_k] + _j; 
					if (!valid(x, y) || a[x][y]) continue;
					int i = b[_i][_j], j = b[x][y], k = 0;
					for (int z = 0; z < 8; z ++) {
						int xx = dx[z] + _i, yy = dy[z] + _j;
						if (!valid(xx, yy) || a[xx][yy]) continue; 
						int dis = max(abs(xx - x), abs(yy - y));
						if (dis <= 1) 
							i --, j --, k += (dis != 0); 
					}
					g[b[_i][_j]][b[x][y]][0][c[_i][_j]][c[x][y]] --;
					g[i][j][k][c[_i][_j]][c[x][y]] ++;
				}
			}
	int sum = 0, sum2 = 0; 
	for (int i = 0; i <= 8; i ++) 
		for (int p = 0; p <= 8 - i; p ++)
			if (cnt[i][p]) {
				int cnt1 = 0, cnt2 = 0; 
				for (int j = 0; j <= i; j ++) {
					cnt1 = add(cnt1, mul(mul(C(i, j), C(T - i - 1, W - j)), add(j, p)));
					cnt2 = add(cnt2, mul(mul(C(i, j), C(T - i - 1, W - j)), qpow(add(j, p), 2)));
				}
				sum = add(sum , mul(cnt1, cnt[i][p])),
				sum2= add(sum2, mul(cnt2, cnt[i][p]));
			}

	int sum3 = 0; 
	for (int i = 0; i <= 8; i ++)
		for (int j = 0; j <= 8; j ++)
			for (int k = 0; k <= 8 - i; k ++)
				for (int p = 0; p <= 8 - i; p ++)
					for (int q = 0; q <= 8 - j; q ++)
						if (g[i][j][k][p][q]) {
							int cnt3 = 0;
							for (int _p = 0; _p <= i; _p ++)
								for (int _q = 0; _q <= j; _q ++)
									for (int _k = 0; _k <= k; _k ++)
										cnt3 = add(cnt3, mul(mul(mul(C(i, _p), C(j, _q)), mul(C(k, _k), C(T - i - j - k - 2, W - _p - _q - _k))), mul(add(_p, add(_k, p)), add(_q, add(_k, q)) )) );
						
							sum3 = add(sum3, mul(cnt3, g[i][j][k][p][q])); 				
						}
	int invs = qpow(C(T, W), mod - 2), E = mul(sum, invs), D = add(mul(add(sum2, sum3), invs), - qpow(E, 2));
	cout << E << ' ' << D << endl; 
	return 0;
}