[UOJ #422.] 【集训队作业2018】小Z的礼物

UOJ #422.

很显然可以套一个Min-Max容斥

设$\min(S)$为$S$中第一个元素出现的时间,$\max(S)$是$S$中最后一个出现的世界,则有

$$\max(S) = \sum\limits_{T\subsetneq S}\min(T)(-1)^{|T| + 1}$$

然后就是要求每个集合中第一个元素的出现时间

设$f(T)$为包含$T$中任意元素的块数,要暴力的话当然可以直接$\frac{f(T)}{2nm – n – m}$

那么做一个轮廓线DP并且直接把容斥系数记进去就行了

#include <iostream>
#include <cstdio>
#include <cstring>

#define MOD 998244353

template <typename T> void add(T &_, T __){
	_ = (_ + __) % MOD;
}

template <typename T> T ksm(T x, T y){
	T z = 1;
	for(; y; y>>=1, x = 1ll*x*x%MOD)
		if(y & 1) z = 1ll*x*z%MOD;
	return z;
}

int n, m, f[2][(1 << 6) + 1][4010];
char map[15][110];

int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++)
		scanf("%s", map[i] + 1);
	int lim = 2*n*m - n - m, t = 1;
	f[0][0][0] = MOD - 1;
	auto r = [](int S, int p, int b){
		if(((S >> (p-1)) & 1) == b) return S;
		return S ^ (1 << (p - 1));
	};
	for(int i = 1; i <= m; i++)
		for(int j = 1; j <= n; j++, t ^= 1){
			memset(f[t], 0, sizeof(f[t]));
			for(int S = 0; S < 1 << n; S++)
				for(int k = 0; k <= lim; k++){
					add(f[t][r(S, j, 0)][k], f[t^1][S][k]);
					if(map[j][i] == '*'){
						int pls = 0;
						if(j > 1) pls += ((S >> (j-2)) & 1) ^ 1;
						if(i > 1) pls += ((S >> (j-1)) & 1) ^ 1;
						pls += (i < m) + (j < n);
						add(f[t][r(S, j, 1)][k + pls], MOD - f[t^1][S][k]);
					}
				}
		}
	int ans = 0;
	for(int i = 0; i <= lim; i++){
		int res = 0;
		for(int j = 0; j < (1 << n); j++)
			res = (res + f[t ^ 1][j][i]) % MOD;
		ans = (ans + 1ll * res * ksm(i, MOD - 2) % MOD) % MOD;
	}
	ans = 1ll * ans * lim % MOD;
	printf("%d\n", ans);
	return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注