夏晓光(loveJY)的博客

容斥DP

首先套一个min-max容斥

由期望的线性型我们得到

$ans=\sum(-1)^{|T|+1}f(T)$

f(T)表示物品T集合最小的被覆盖时间

这个式子可以$O(2^T*T)$QAQ

然后我们要优化必须要来一个容斥DP算法了...

考虑$f_{i,j,S}$表示dp到点(i,j)然后得到的轮廓线上选或没选状态是S,带容斥系数的方案数是什么

因为T变大当且仅当我们多选了所以可以转移

然而你会发现我们算不了答案,因为我们还是不知道我们的$f(T)$

解决方法是你会发现这个时间本质上是最多有多少个1*2的子矩阵满足包括了T中的物品,设为k

然后期望步数就是$n*(m-1)+m*(n-1)/k$

这样我们再多记一维就好了QAQ,表示当前有多少个1*2子矩阵是包含T中物品的,注意计算k的变化

时间复杂度$O(2^nn^2m^2)$

我竟然码出来了

code:

//轮廓线容斥dp
//我一定能写出来!
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXL = 103;
const int MAXH = 7;
const int MAXS = (1 << 6) + 1;
const int MAXP = MAXL * MAXH * 2;
const int MAXN = 1e4 + 7;
const int P = 998244353;
int n, m, p, maxs;
int dp[MAXL][MAXH][MAXS][MAXP], a[MAXH][MAXL];
int fac[MAXN], ifac[MAXN];
char s[MAXL];

inline ll ksm(ll x, ll y) {
	ll ans = 1;
	while(y) {
		if(y & 1)ans = ans * x % P;
		x = x * x % P;
		y >>= 1;
	}
	return ans;
}

inline void add(int &x, ll y) {
	x += y;
	if(x >= P)
		x -= P;
}

inline void init() {
	fac[0] = 1;
	ifac[0] = ifac[1] = 1;
	for(int i = 1; i <= p; ++i) {
		fac[i] = 1ll * fac[i - 1] * i % P;
	}
	ifac[p] = ksm(fac[p], P - 2);
	for(int i = p - 1; i >= 2; --i) {
		ifac[i] = 1ll * ifac[i + 1] * (i + 1) % P;
	}
	// printf("%d ? %d %d\n", ifac[2], fac[4], 1ll * ifac[5]*fac[5] % P);
	for(int i = 1; i <= p; ++i) {
		ifac[i] = 1ll * ifac[i] * fac[i - 1] % P;
		// printf("%lld?\n", 1ll * ifac[i] * i % P);
	}
}

int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i) {
		scanf("%s", s + 1);
		for(int j = 1; j <= m; ++j) {
			if(s[j] == '*') {
				a[i][j] = 1;//第一维小,第二维大
			}
		}
	}
	p = n * (m - 1) + m * (n - 1);
	init();
	maxs = (1 << n) - 1;//qwq
	dp[1][1][0][0] = P - 1;
	//第几列,第几行,轮廓线状态为(1)在T中,有多少个点对
	for(int i = 1; i <= m; ++i) {
		for(int j = 1; j <= n; ++j) {
			for(int S = 0; S <= maxs; ++S) {
				for(int k = 0; k <= p; ++k) {
					if(dp[i][j][S][k]) {
						// printf("we are in :%d %d %d %d qwq%d\n ", i, j, S, k, dp[i][j][S][k]);
						if(a[j][i]) {
							int nS = S | (1 << (j - 1));
							int nk = k;//一定多出
							if(i < m)nk++;//下一列
							if(j < n)nk++;//下一行
							if(i > 1)nk += (S >> (j - 1) & 1) ^ 1;//如果不是第一列,可以从之前转移
							if(j > 1)nk += (S >> (j - 2) & 1) ^ 1;//如果不是第一行,可以从上一格转移
							// printf("now nS is :%d nk is: %d naddV is: %d\n", nS, nk, P - dp[i][j][S][k]);
							if(j != n)add(dp[i][j + 1][nS][nk], P - dp[i][j][S][k]);//多了一个,集合变大,所以变成负数
							else add(dp[i + 1][1][nS][nk], P - dp[i][j][S][k]);
						}
						// puts("");
						//j,i不是格子
						int nS = S & (S ^ (1 << (j - 1)));
						// printf("now nS is :%d nk is: %d naddV is: %d\n", nS, k, dp[i][j][S][k]);
						if(j != n)add(dp[i][j + 1][nS][k], dp[i][j][S][k]);
						else add(dp[i + 1][1][nS][k], dp[i][j][S][k]);
						// puts("\n");
					}
				}
			}
		}
	}
	int ans = 0;
	for(int S = 0; S <= maxs; ++S)
		for(int i = 1; i <= p; ++i) {
			// printf("%d %d %d %d\n", S, i, dp[m + 1][1][S][i], ifac[i]);
			add(ans, 1ll * dp[m + 1][1][S][i] * ifac[i] % P * p % P);
		}
	printf("%d\n", ans);
	return 0;
}