ARC093F Dark Horse

发表于 | 分类于

Description

有\(2^n\)个用\(1\ldots 2^n\)编号的的人，你需要将他们排成一排，然后两两对战，胜出者再按照在原序列中的顺序排成一排，再用上述方法淘汰，直到只剩下一个人。

至于两人比赛的规则，假设比赛的两个人的编号为\(x\)和\(y\)，那么编号小者胜出。但是特别的，有\(m\)个人，他们一定可以击败\(1\)（但是他们在和其他人作战时按照上述规则）。

求问有多少种安排排列的方法，使得\(1\)最终胜出。

\(1\leq n\leq 16, 0\leq m < \min(2^n, 17)\)。

Solution

你事，一个，一个，一个数数题，，，（池沼）

我们队序列建一个满二叉树，那么很显然一个节点就代表了所在子树的最终胜出者。那么我们不妨固定\(1\)在头上（接下来我们会发现其他情况都是一样的，所以最终乘一个\(2^n\)就行），倘使有\([2, 2], [3, 4],\ldots,[2^{n - 1} + 1, 2^n]\)这\(n\)个区间所代表的节点不能为给定的\(m\)个人，那么\(1\)就能胜出。

但这样直接计数还是要飞，那么就容斥吧！

注意到我们只需要去限制\(n\)个节点，所以看起来状压DP是一个不错的决定。我们不妨将\(A\)从小到大排序，然后定义状态\(f_{i, s}\)表示考虑\(A_{i\ldots m}\)这些人，目前确定了至少集合\(s\)中的线段树节点的胜出点在考虑的人当中。转移的话就考虑\(A_i\)是否对\(s\)造成了贡献即可。最后对所有至少的集合容斥，然后就能得到恰好空集的情况，这也算是传统艺能力，，，

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <utility>
const int maxn = 22;
using ll = long long;
const ll ha = 1000000007LL;
ll pow_mod(ll a, ll b) {
  ll ans = 1, res = a;
  while(b) {
    if(1LL & b) ans = ans * res % ha;
    res = res * res % ha; b >>= 1;
  }
  return ans;
}
ll inv(ll x) {
  return pow_mod(x, ha - 2LL);
}

ll fac[1 << 20], ifac[1 << 20];
void process() {
  fac[0] = 1;
  const int n = (1 << 20) - 1;
  for(int i = 1; i <= n; i ++) {
    fac[i] = fac[i - 1] * (ll)i % ha;
  }
  ifac[n] = inv(fac[n]);
  for(int i = n - 1; i >= 0; i --) {
    ifac[i] = ifac[i + 1] * (ll(i + 1)) % ha;
  }
}
ll C(int n, int m) {
  if(n < m) return 0;
  ll ret = fac[n] * ifac[n - m] % ha;
  ret = ret * ifac[m] % ha;
  return ret;
}

int A[maxn]; ll f[1 << 20];
int main() {
  process();
  int n, m; scanf("%d%d", &n, &m);
  for(int i = 1; i <= m; i ++) {
    scanf("%d", &A[i]);
  }
  std::sort(A + 1, A + 1 + m); f[0] = 1;
  for(int i = m; i >= 1; i --) {
    for(int s = (1 << n) - 1; s >= 0; s --) {
      int sum = 0;
      for(int j = 0; j < n; j ++) {
        if((1 << j) & s) sum += (1 << j);
      }
      ll res = (1 << n) - sum - A[i];
      for(int j = 0; j < n; j ++) {
        if(((1 << j) & s) == 0) {
          ll delta = f[s] * C(res, (1 << j) - 1) % ha;
          delta = delta * fac[1 << j] % ha;
          int v = s | (1 << j);
          f[v] += delta;
          if(f[v] >= ha) f[v] -= ha;
        }
      }
    }
  }
  ll ans = 0;
  for(int s = 0; s < (1 << n); s ++) {
    int cnt = 0, sum = 0;
    for(int i = 0; i < n; i ++) {
      if((1 << i) & s) {
        cnt ++; sum += (1 << i);
      }
    }
    ll delta = f[s] * fac[(1 << n) - sum - 1] % ha;
    if(1 & cnt) delta = (ha - delta) % ha;
    ans = (ans + delta) % ha;
  }
  ans = ans * (ll(1LL << n)) % ha;
  printf("%lld\n", ans);
  return 0;
}