526互联

AtCoder Beginner Contest 215 H Cabbage Master

发布时间 2023-06-14 13:32:11作者: zltzlt

洛谷传送门

AtCoder 传送门

考虑第一问。

发现这个东西长得很像二分图匹配，考虑建图，第 \(i\) 个盒子建 \(b_i\) 个左部点，第 \(i\) 个球建 \(a_i\) 个右部点，每个盒子的每个点往可以放的球的每个点连边。显然要求能被满足等价于，这个二分图存在一个左部点的完全匹配。

因为一个盒子的点本质相同，可以放一起考虑。根据 Hall 定理，要求能被满足的充要条件是 \(\forall T \subseteq \{1, 2, ..., m\}, \sum\limits_{x \in T} b_x \le \sum\limits_{x \in N(T)} a_x\)，其中 \(N(T)\) 为 \(T\) 连向的右部点集合。

现在想删除最少个数的点，使得这个条件不满足。显然答案是 \(\min\limits_{T} (\sum\limits_{x \in N(T)} a_x - \sum\limits_{x \in T} b_x + 1)\)。

但是显然不能直接枚举 \(T\)。考虑枚举 \(N(T)\)，那么对应的 \(\sum\limits_{x \in T} b_x\) 可以一遍高维前缀和求出。设 \(f_S = \sum\limits_{i \in S} a_i, g_S = \sum\limits_{N(\{x\}) \subseteq S} b_x\)，那么第一问的答案是 \(M = \min\limits_S\{f_S - g_S + 1 \mid g_S > 0\}\)。\(g_S > 0\) 是因为 \(S = N(T)\) 要存在。

考虑第二问。

一个简单的想法是，枚举满足 \(f_S - g_S + 1 = M\) 的集合 \(S\)，把 \(\binom{f_S}{M}\) 求和。但是这样会算重，因为所有满足 \(f_S - g_S + 1 = M\) 的集合 \(S\) 有重叠部分。

不妨枚举删除的点所在集合 \(S\)，设 \(h_S\) 为在 \(S\) 中选 \(M\) 个点，并且每个在 \(S\) 中的球都至少被选一个。答案即 \(\sum\limits_{S} [\exists T \supseteq S, f_T - g_T + 1 = M] h_S\)。

\(d_S = [\exists T \supseteq S, f_T - g_T + 1 = M]\) 可以高维前缀和求得。问题还剩下求 \(h_S\)。

考虑容斥，枚举 \(P \subseteq S\)，钦定属于 \(P\) 的球不能被选，其余任意，我们得到 \(h_S = \sum\limits_{P \subseteq S} (-1)^{|P|} \binom{f_S - f_P}{M} = \sum\limits_{P \subseteq S} (-1)^{|S| - |P|} \binom{f_P}{M}\)。这个也可以高维前缀和求，每添加一位就取相反数即可。

时间复杂度是 \(O(2^n n)\) 的。

code 
// Problem: H - Cabbage Master
// Contest: AtCoder - AtCoder Beginner Contest 215
// URL: https://atcoder.jp/contests/abc215/tasks/abc215_h
// Memory Limit: 1024 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 10050;
const int maxm = 2000100;
const int N = 2000000;
const ll mod = 998244353;

inline ll qpow(ll b, ll p) {
	ll res = 1;
	while (p) {
		if (p & 1) {
			res = res * b % mod;
		}
		b = b * b % mod;
		p >>= 1;
	}
	return res;
}

ll n, m, a[maxn], b[maxn], c[22][maxn], d[maxm], f[maxm], g[maxm], h[maxm];
ll fac[maxm], ifac[maxm];

inline void init() {
	fac[0] = 1;
	for (int i = 1; i <= N; ++i) {
		fac[i] = fac[i - 1] * i % mod;
	}
	ifac[N] = qpow(fac[N], mod - 2);
	for (int i = N - 1; ~i; --i) {
		ifac[i] = ifac[i + 1] * (i + 1) % mod;
	}
}

inline ll C(ll n, ll m) {
	if (n < m || n < 0 || m < 0) {
		return 0;
	} else {
		return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
	}
}

void solve() {
	scanf("%lld%lld", &n, &m);
	for (int i = 1; i <= n; ++i) {
		scanf("%lld", &a[i]);
	}
	for (int i = 1; i <= m; ++i) {
		scanf("%lld", &b[i]);
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			scanf("%lld", &c[i][j]);
		}
	}
	for (int i = 1; i <= m; ++i) {
		int S = 0;
		for (int j = 1; j <= n; ++j) {
			if (c[j][i]) {
				S |= (1 << (j - 1));
			}
		}
		g[S] += b[i];
	}
	for (int i = 0; i < n; ++i) {
		for (int S = 0; S < (1 << n); ++S) {
			if (S & (1 << i)) {
				g[S] += g[S ^ (1 << i)];
			}
		}
	}
	ll mn = 1e18;
	for (int S = 1; S < (1 << n); ++S) {
		for (int i = 1; i <= n; ++i) {
			if (S & (1 << (i - 1))) {
				f[S] += a[i];
			}
		}
		if (g[S]) {
			if (f[S] < g[S]) {
				puts("0 1");
				return;
			}
			mn = min(mn, f[S] - g[S] + 1);
		}
	}
	for (int S = 1; S < (1 << n); ++S) {
		h[S] = C(f[S], mn);
		if (f[S] - g[S] + 1 == mn) {
			d[S] = 1;
		}
	}
	for (int i = 0; i < n; ++i) {
		for (int S = 0; S < (1 << n); ++S) {
			if (S & (1 << i)) {
				h[S] = (h[S] - h[S ^ (1 << i)] + mod) % mod;
				d[S ^ (1 << i)] += d[S];
			}
		}
	}
	ll ans = 0;
	for (int S = 1; S < (1 << n); ++S) {
		if (d[S]) {
			ans = (ans + h[S]) % mod;
		}
	}
	printf("%lld %lld\n", mn, ans);
}

int main() {
	init();
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}