ARC093D Dark Horse (计数&容斥dp)题解

发布于 2021-03-29  307 次阅读


本文同步发表在我的洛谷博客,Mathjax炸了可以去那边。

题目大意:

有 $2^N$ 个人,按照满二叉树的形态进行淘汰赛,一开始的排列顺序为所有 $(2^N)!$ 个排列之一。
你是第 $1$ 个人,已知每一对人之间的实力关系,具体地说:
给出 $M$ 个人 $A_1 \sim A_M$ , 这 $M$ 个人都打得过你。
你打得过除了这 $M$ 个人之外的所有其他人。
对于剩下的情况(你不参与的情况),编号小的人胜利。
问你在所有的 $(2^N)!$ 种情况中,有多少种情况可以取得最终胜利。答案对 ${10}^9 + 7$ 取模。
$ 1 \le n ,m \le 16 $

解题思路:

首先我们画张图:

可以发现不管自己这个人在哪个叶子结点,我们对于答案的贡献是一定的。
所以我们把自己固定在 $1$ ,最后算出的答案乘上 $2^n$ 就可以了。

那么如果我们在 $1$ ,我们可以对其他人进行分组,发现会与我们交手的人就是每组的最小值(如上图就是组的分配)。

设 $G_i$ 为第 $i$ 组,则可以发现:$G_i={ p_{2^i+1} ... p_{2^{i+1}}}$ ,且总共有 $n$ 个组。注意这里组从 0 开始编号会比较方便一点。

那么我们的任务就变成了使每个组里面的最小值都不为 $A$ 中的元素 (否则因为没有自己参与的情况是编号小的赢,那么此时 $A$ 中的那个元素会突出重围然后把你干掉)。

我们考虑正难则反。我们设 $f(S)$ (S中的每一位为 0 或 1)表示 $S$ 中对应位置上为 1 的组里面最小值为 $A$ 中的元素时的排列数。

那么我们考虑对答案进行容斥(因为最后答案只需要存在一组里面最小值为 $A$ 里的元素就行了)。那么最终答案就是:

$$
ans=2^n \times (\sum_S (-1)^{popcount(S)} f(S))
$$
其中 $popcount(S)$ 为 $S$ 中 $1$ 的个数。

那么我们考虑如何求出 $f(S)$ 。此时我们先对 $A$ 从大到小进行排序,至于为什么下面会讲。我们设 $dp_{i,S}$ 表示进行到 $A$ 中的第 $i$ 个人,此时的 $S$ 状态中所有为 $1$ 的组已经被填满了,而且最小值为 $A$ 中的数(即当前组必败),其他的位置还没有填过的排列数。
这个状态很妙啊,尤其是 $S$ 这一维啊。为什么呢?因为 $S$ 中每个为 $1$ 的组都是装满的,那么 $S$ 的二进制下的值也就等于 $S$ 中已经分配好的人数。

那么对于当前的 $A_i$ ,我们有两种分配方式:

  1. 把它放进一个已经分配好的组里,那么因为 $A$ 是从大到小放的,所以当前的 $A_i$ 放进去后可以保证当前组里的最小值还是 $A$ 中的元素(假设原来在这个组里的是 $A_j$ ,则原来满足其他元素都大于 $A_j$ ,那么更满足其他元素都大于 $A_i$ 了)。 转化为式子就是 $dp_{i,S}+=dp_{i-1,S}$ 。

  2. 选一个没有分配好的组 $k$ , $1 \le k \le n$,我们把 $A_i$ 塞进这个组里,再找 $2^k-1$ 个吃瓜群众陪跑。注意这里的吃瓜群众编号必须比 $A_i$ 大,而且最后这些吃瓜群众可以自由排列,所以还得乘上一个阶乘。转移方程就是:$dp_{i,S|2^k}+=(f_{i-1,S} \times \tbinom{2^n-S-A_i}{2^k-1}*(2^k)!)$

诶我们有了 $dp_{i,S}$ ,那么就知道了 $f(S)$ :
$$
f(S)=dp_{m,S} \times (2^n-1-S)!
$$
因为除了分配好的组外,其他的人也可以自由排列。

时间复杂度为 $O(nm2^n)$ 。

Code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int Mod=1000000007;
const int N=25,M=(1<<17)+5;

int n,m,a[N];
ll fac[M],inv[M],f[N][M];

inline int read(){
    int x=0,f=1; char ch=getchar();
    while (!isdigit(ch)) { if (ch=='-') f=-1; ch=getchar(); }
    while (isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); }
    return x*f;
}

inline int popcount(int x){
    int res=0;
    while (x){
        res+=(x&1);
        x>>=1;
    }
    return res;
}

inline void Prepare(){
    fac[0]=inv[0]=inv[1]=1;
    for (int i=1;i<=M-5;++i) fac[i]=fac[i-1]*i%Mod;
    for (int i=2;i<=M-5;++i) inv[i]=(Mod-Mod/i)*inv[Mod%i]%Mod;
    for (int i=2;i<=M-5;++i) inv[i]=inv[i]*inv[i-1]%Mod;
}

inline ll C(int n,int m){
    if ((n<m) || (m<0)) return 0;
    else return fac[n]*inv[m]%Mod*inv[n-m]%Mod;
}

int main(){
    //freopen("ARC093D.in","r",stdin);
    //freopen("ARC093D.out","w",stdout);
    n=read(),m=read();
    for (int i=1;i<=m;++i)
        a[i]=read();
    Prepare();
    sort(a+1,a+m+1,greater<int>());
    f[0][0]=1;
    for (int i=1;i<=m;++i)
        for (int S=0;S<(1<<n);++S){
            f[i][S]=(f[i][S]+f[i-1][S])%Mod;
            for (int k=0;k<n;++k){
                if ((S>>k)&1) continue;
                f[i][S|(1<<k)]=(f[i][S|(1<<k)]+f[i-1][S]*C(((1<<n)-S-a[i]),(1<<k)-1)%Mod*fac[1<<k]%Mod)%Mod;
            }
        }
    ll ans=0;
    for (int S=0;S<(1<<n);++S){
        int x=popcount(S);
        if (x%2) ans=(ans-(f[m][S]*fac[(1<<n)-S-1]%Mod)+Mod)%Mod;
        else ans=(ans+(f[m][S]*fac[(1<<n)-S-1]%Mod))%Mod;
    }
    printf("%lld\n",ans*(1<<n)%Mod);
    return 0;
}

这么好的博客不点个赞支持支持吗/QvQ


我们无法选择过去,但我们可以改变未来。