[AtCoder ARC093F]Dark Horse

题目大意：有$2^n$个人，每相邻的两个人比赛一次。令两个人的编号为$a,b(a\leqslant b)$，若$a\neq 1$，则$a$的人获胜；否则若$b\in S$则$b$获胜，不然$1$获胜。钦定$1$获胜，问可以的开始的顺序的方案数

题解：状压$DP$，令开始的第$i$位的人的编号为$p_i$，发现到只有$\min\limits_{i\in[2^{j-1}+1,2^j]}\{p_i\}(1\leqslant j\leqslant n)$的人会和$1$打，考虑容斥，令$f_{i,j}$为到了要放$S$中的第$i$个人，现在第$k$个段（$[2^{k-1}+1,2^k]$）中的最小值在$S$中的状态为$1<<k \& j$，时可以战胜$1$的方案数。（发现一个很优美的东西，$j==已经放置的人数$）

卡点：无

C++ Code：

#include <cstdio>

#define N 1 << 16 | 3

const int mod = 1000000007;

int n, m, s[20];

long long fac[N], inv[N];

long long f[17][N], ans, U;

void update(long long &x, long long y) {if ((x += y) >= mod) x -= mod;}

long long C(long long a, long long b) {

	if (a < b) return 0;

	return fac[a] * inv[b] % mod * inv[a - b] % mod;

}

int main () {

	scanf("%d%d", &n, &m); U = 1 << n;

	for (int i = 1; i <= m; i++) scanf("%d", s + m - i);

	fac[0] = fac[1] = inv[0] = inv[1] = 1;

	for (int i = 2; i < U; i++) {

		fac[i] = fac[i - 1] * i % mod;

		inv[i] = inv[mod % i] * (mod - mod / i) % mod;

	}

	for (int i = 2; i < U; i++) inv[i] = inv[i - 1] * inv[i] % mod;

	f[0][0] = 1;

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

		for (int j = 0; j < U; j++) {

			update(f[i + 1][j], f[i][j]);

			for (int k = 0; k < n; k++) {

				if (!(j & (1 << k))) update(f[i + 1][j | 1 << k], f[i][j] * fac[1 << k] % mod * C(U - j - s[i], (1 << k) - 1) % mod);

			}

		}

	}

	for (int i = 0; i < U; i++) {

		long long tmp = f[m][i] * fac[U - i - 1] % mod;

		update(ans, __builtin_parity(i) ? (mod - tmp) : tmp);

	}

	printf("%lld\n", ans * U % mod);

	return 0;

}

巴特西

[AtCoder ARC093F]Dark Horse

最新文章

热门文章