ARC093F Dark Horse 题解

作者: xht37 分类: 题解 发布时间: 2020-04-23 16:21

Visits: 260

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;
}

发表评论

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