[数学记录]AT3981 [ARC093D] Dark Horse

· · 个人记录

题意 :

有 2^n 个人，按照满二叉树的形态进行淘汰赛，一开始的排列顺序为所有 (2^n)! 个排列之一。

你是第 1 个人，已知每一对人之间的实力关系，具体地说：

问你在所有的 (2^n)! 种情况中，有多少种情况可以取得最终胜利。答案对 10^9 + 7 取模。

------------ 将比 $1$ 强的 $m$ 个人称为大佬。 首先将 $1$ 放在第一个位置，最后将答案乘以 $2^n$。 每个人都只会参与恰好 $n$ 场对局，而你只需要保证这 $n$ 场中没有遇到大佬。 各个对局分别对应大小为 $1,2,4,\dots 2^{n-1}$ 的子树。 考虑容斥。钦定对局集合 $S$，则要在对应子树中安排选手，使得被钦定的子树的最小值是大佬。 记方案数为 $g(S)$ ，则答案为 $2^n\sum\limits_{S}(-1)^{|S|}g(S)$。 考虑状压 $\rm DP$ ，按照编号从大到小的顺序考虑大佬（因为编号越大限制越强）。 设 $f[i,s]$ 为考虑了前 $i$ 个大佬，且子树集合 $s$ 被覆盖的贡献和。 在安排第 $i$ 个大佬时，可以不加入，也可以处理某个子树。 记 $siz(s)=\sum\limits_{j\in s}2^j$ ，即已经被安排好的子树大小和。 转移 : $f[i,s]=f[i-1,s]-\sum\limits_{j\in s}f[i-1,s-\{j\}]\big(2^n-A_i-siz(s-\{j\})\big)^{\underline {2^j-1}}2^j

其中 \big(2^n-A_i-siz(s-\{j\})\big)^{\underline {2^j-1}} 是选出未被占用的比 A_i 大的 2^j-1 个垫背者，最后将 A_i 加入有 2^j 种方法。

其中下降幂可以预处理阶乘后快速计算。

边界 : f[0,\varnothing]=1

最终需要考虑剩余数的排列，有 g(s)=f[n,s]\big(2^n-1-siz(s)\big)!

复杂度 O(nm2^n)。（所以其实 m 大一点也没关系的?）

#include<algorithm>
#include<cstdio>
#define ll long long
#define MaxS 66000
using namespace std;
const int mod=1000000007;
ll powM(ll a,int t=mod-2){
  ll ret=1;
  while(t){
    if (t&1)ret=ret*a%mod;
    a=a*a%mod;t>>=1;
  }return ret;
}
ll fac[MaxS],ifac[MaxS];
ll dpow(int k,int n)
{return k<n ? 0 : fac[k]*ifac[k-n]%mod;}
void Init(int n)
{
  fac[0]=1;
  for (int i=1;i<=n;i++)
    fac[i]=fac[i-1]*i%mod;
  ifac[n]=powM(fac[n]);
  for (int i=n;i;i--)
    ifac[i-1]=ifac[i]*i%mod;
}
ll f[18][MaxS];
int cnt(int s){
  int ret=0;
  while(s){s^=s&-s;ret++;}
  return ret;
}
int n,m,a[18];
int main()
{
  scanf("%d%d",&n,&m);
  int tot=1<<n;Init(tot);
  for (int i=1;i<=m;i++)scanf("%d",&a[i]);
  reverse(a+1,a+m+1);
  f[0][0]=1;
  for (int i=1;i<=m;i++)
    for (int s=0;s<tot;s++){
      f[i][s]=f[i-1][s];
      for (int j=0;j<n;j++)
        if (s&(1<<j))
          f[i][s]=(f[i][s]+f[i-1][s^(1<<j)]*dpow(tot-a[i]-(s^(1<<j)),(1<<j)-1)%mod*(1<<j))%mod;
    }
  ll ans=0;
  for (int s=0;s<tot;s++){
    ll buf=f[m][s]*fac[tot-1-s]%mod;
    if (cnt(s)&1)ans-=buf;else ans+=buf;
  }ans=(ans%mod+mod)%mod;
  printf("%lld",(ans<<n)%mod);
  return 0;
}