题解：[ARC093F] Dark Horse

· · 题解

AT_arc093_d

题目描述

给定 n，m ，问在有 m 个编号为 a_i 的选手不可战胜的情况下，在一个 2^n 的满二叉树上进行淘汰制比赛，获胜的情况数

具体解释，你是 1 号选手，你无法战胜的选手有且仅有那 m 个，对于剩下的情况（你不参与的情况），编号小的人胜利，选手编号 \le2^n。

题目分析

由于不管 1 在哪个位置，一轮轮下来，基本上过程都是相似的，所以假设 1 在第 1 个位置。

令集合 a 表示无法战胜的选手，集合 p 表示所有选手

它所遇见对手的情况无非是p_1,\min{(p_2,p_3)},\min{(p_4,p_5,p_6,p_7)} ,...

把这些人分别用 b_0,b_1,b_2,... 表示，因此我们要求的就是：使得任意 x\in b 且 x\notin a ，它们的情况数目

发现 \vert b \vert =n ，较小 ，所以想到状压 ， 用 S 表示 ， S 中的 1 表示该位置 b_i\in a ，定义 dp[i][S] 表示集合 S 中的 b 值均出现在 a 中前 i 个数的方案数。

？？？$ 你问我不是要的是 $b,a$ 中元素不相同吗$？

如果真的要这样就太复杂了

那我们反过来 ，考虑容斥 ，定义函数 count(x) 表示 x 在二进制下 1 数量的奇偶性 ， 奇返回 -1 ， 偶返回 1 ， 令 S 上界为 N ， 可以证明最终结果 ans=\sum_{S=0}^{N} count(S)\times dp[m][S]

现在来考虑 dp 的转移 ：

for(int j=0;j<n;j++)
{
    if(!((S>>j)&1))
    {
        les=(1<<n)-a[i]-S;
        dp[i+1][S|(1<<j)]+=dp[i][j]*C(les,(1<<j)-1));   
    }   
}

其中 C(n,m) 表示从 n 个数中选 m 个数的方案数 ，不用多说

为了方便计数 ， 将 $a$ 从大到小排序 最后，由于转移后没有考虑到 $S$ 中剩下 $0$ 中的选择情况 ， 还要乘上 $(2^n-1-S)!$ （也是由此推出容斥原理） 时间复杂度 $O(2^nnm)

code

#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) x&(-x)
using namespace std;
const int N=20,K=(1<<16)+7,p=1e9+7;
int n,m;
int a[N];
ll dp[N][K],ans;
ll fac[K],inv[K];
ll qpow(ll x,int n,ll res=1)
{
    while(n)
    {
        if(n&1) res=res*x%p;
        x=x*x%p;
        n>>=1;
    }
    return res;
}
bool cmp(int a,int b)
{
    return a>b;
}
void init(int n)
{
    fac[0]=inv[0]=1;
    for(int i=1;i<=n;i++)   fac[i]=fac[i-1]*i%p;
    inv[n]=qpow(fac[n],p-2);
    for(int i=n-1;i>=1;i--) inv[i]=inv[i+1]*(i+1)%p;
}
ll C(int n,int m)
{
    if(n<m) return 0;
    return fac[n]*inv[m]%p*inv[n-m]%p;
}
int get_cnt(int x,int ans=0)
{
    while(x)
    {
        ans++;
        x-=lowbit(x);
    }
    return ans;
}
int main()
{
    scanf("%d%d",&n,&m);init(1<<n);
    for(int i=1;i<=m;i++)   scanf("%d",&a[i]);
    sort(a+1,a+m+1,cmp);
    dp[0][0]=1;
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<(1<<n);j++)
        {
            int t=(1<<n)-a[i+1]-j;
            dp[i+1][j]=(dp[i+1][j]+dp[i][j])%p;
            for(int k=0;k<n;k++)
            {
                if(!((j>>k)&1))
                {
                    dp[i+1][j|(1<<k)]=(dp[i+1][j|(1<<k)]+dp[i][j]*C(t,(1<<k)-1)%p*fac[1<<k]%p)%p;
                }
            }
        }
    }
    int S=(1<<n)-1;
    for(int i=0;i<=S;i++)
    {
        int cnt=get_cnt(i);
        if(cnt&1)   ans=(ans-dp[m][i]*fac[S-i]%p+p)%p;
        else    ans=(ans+dp[m][i]*fac[S-i]%p)%p;
    }
    ans=ans*(S+1)%p;
    printf("%d",ans);
    return 0;
}

是不是发现最后 ans 乘上了一个 2^n ，因为 1 可以出现在 2^n 个位置