【集训队作业2018】小Z的礼物

时间：2021-06-02 21:48:18

小水题。题意就是不断随机放一个 \(1 \times 2\) 骨牌，然后取走里面的东西。求期望多少次取走所有的东西。然后有一维很小。

首先显然 minmax 容斥，将最后取走转化为钦定一些物品，求第一个取走的期望。

然后显然第一个取走的期望只和剩下能盖到物品的骨牌数有关。

一个骨牌能盖到物品只和相邻的两个格子是否钦定了物品有关。这个显然可以轮廓线优化。

然后套用 minmax 容斥公式直接算出来。

复杂度 \(O\left(n^2m^2 2^n\right)\)

数组清空写错了，导致 dp 状态 disappeared……调了好一会……

#include <bits/stdc++.h>

const int mod = 998244353;

typedef long long LL;

void reduce(int & x) { x += x >> 31 & mod; }

int mul(int a, int b) { return (LL) a * b % mod; }

int fastpow(int a, int b, int res = 1) {

	for (; b; b >>= 1, a = mul(a, a)) if (b & 1) res = mul(res, a);

	return res;

}

int dp[2][1 << 6][1200], ansl[1200];

int n, m;

bool mat[110][10];

char buf[110];

int main() {

	std::ios_base::sync_with_stdio(false), std::cin.tie(0);

	std::cin >> n >> m;

	const int E = n * (m - 1) + m * (n - 1);

	for (int i = 0; i != n; ++i) {

		std::cin >> buf;

		for (int j = 0; j != m; ++j)

			mat[j][i] = buf[j] == '*';

	}

	const int U = 1 << n;

	int lst = 0, now = 1;

	dp[now][0][0] = mod - 1;

	for (int i = 0; i != m; ++i) {

		for (int j = 0; j != n; ++j) {

			std::swap(lst, now);

			for (int k = 0; k < U; ++k)

				memset(dp[now][k], 0, E + 1 << 2);

			bool can = mat[i][j];

			for (int l = 0; l != U; ++l) {

				int delta = 0;

				if (i) delta += ~l >> j & 1;

				if (j) delta += ~l >> j - 1 & 1;

				int tar = l & ~(1 << j), tar2 = tar | 1 << j;

				for (int k = 0; k <= E; ++k)

					if (int t = dp[lst][l][k]) {

						reduce(dp[now][tar][k + delta] += t - mod);

						if (can) reduce(dp[now][tar2][k] -= t);

					}

			}

		}

	}

	for (int i = 0; i != U; ++i)

		for (int j = 0; j <= E; ++j)

			reduce(ansl[j] += dp[now][i][j] - mod);

	int ans = 0;

	for (int i = 0; i < E; ++i)

		reduce(ans += fastpow(E - i, mod - 2, ansl[i]) - mod);

	ans = mul(ans, E);

	std::cout << ans << std::endl;

	return 0;

}

相关文章