ARC093F Dark Horse 题解

ARC093F Dark Horse

题意

• 有 $2^n$ 个人，编号为 $1 \sim 2^n$，他们要进行一场比赛。
• 他们首先会排成一排形成一个排列，然后每一轮第 $2k-1$ 和第 $2k$ 个人对抗，留下胜利者，最终留下的人是冠军。
• 另有一个大小为 $m$ 的编号集合 $S$，编号为 $x,y(x<y)$ 的对抗结果如下：
  • 若 $x = 1$ 且 $y \in S$，则 $y$ 胜。
  • 否则 $x$ 胜。
• 求能使得编号为 $1$ 的人成为冠军的排列数。
• $n,m \le 16$，$1 \notin S$，答案对 $10^9+7$ 取模。

题解

$1$ 要成为冠军必须打败 $n$ 个对手，第 $i$ 个对手来自大小为 $2^{i-1}$ 的子树中，也就是 $2^{i-1}$ 个数中的 $\min$。

于是问题变成求将 $2 \sim 2^n$ 这 $2^n-1$ 个数划分成 $n$ 个集合，第 $i$ 个集合中有 $2^{i-1}$ 个数，每个集合中的 $\min \notin S$ 的方案数，然后乘上 $2^n \prod_{i=1}^n 2^{i-1}!$。

考虑容斥，对于一个状态 $s$，若第 $i$ 个集合的 $\min \in S$，则将 $s$ 的第 $i-1$ 位设为 $1$。

最终答案为 $\sum_{s=0}^{2^n-1} (-1)^{|s|} f(s)$，其中 $f(s)$ 表示状态为 $s$ 的方案数，可以通过对 $S$ 中的数从大到小 DP 预处理出，总时间复杂度 $\mathcal O(2^nnm)$。

代码

const int N = 16;
int n, m, a[N|1];
modint f[N|1][1<<N|1], ans;

int main() {
	rd(n, m), rda(a, m);
	reverse(a + 1, a + m + 1);
	init(1 << n);
	f[0][0] = 1;
	for (int i = 1; i <= m; i++)
		for (int j = 0; j < (1 << n); j++) {
			f[i][j] += f[i-1][j];
			for (int k = 0; k < n; k++)
				if (!(j >> k & 1))
					f[i][j|1<<k] += f[i-1][j] * binom((1 << n) - a[i] - j, (1 << k) - 1);
		}
	for (int i = 0; i < (1 << n); i++) {
		int s = (1 << n) - 1 - i;
		for (int j = 0; j < n; j++)
			if (!(i >> j & 1)) f[m][i] *= binom(s, 1 << j), s -= 1 << j;
		if (__builtin_popcount(i) & 1) ans -= f[m][i];
		else ans += f[m][i];
	}
	ans *= 1 << n;
	for (int i = 0; i < n; i++) ans *= p[1<<i];
	print(ans);
	return 0;
}