题意

有 $2^N$ 个人打锦标赛,他们的过程是随机一个排列,然后按照这个排列站好。每轮是第 $2_i − 1$ 个人和第 $2_i$ 的人比赛,败者淘汰。 你是 $1$ 号选手,你碰到$A_1,A_2,\cdots,A_m$ 会输,碰到剩下的会赢。如果比赛和你无关,那么编号小的赢。
求有多少个排列,能够使你最后赢。答案对 $10^9 + 7$ 取模。 $1\leq N\leq 16,0\leq M\leq 16,2\leq A_i \leq 2^N$。

题解

对于 $N \leq 4$ 我们可以使用 sb 状压过掉(这也导致了我的思维定式)。
其实这个题也算是套路。首先我们考虑决定一个排列是否胜利的条件是啥:发现将这个排列分成 $N$ 段,第 $i$ 段是 $[2^i,2^{i+1}-1]$。如果这个排列会让 $1$ 胜利当且仅当每一段的编号最小的选手都不能打败 $1$。
那么我们就容斥吧(悲)限制变成了某些区间的最小值是能打败 $1$ 的,其他区间随便填。
设 $f_{i,S}$ 表示从高到低考虑了前 $i$ 个数,$S$ 区间的最小值已经是能打败 $1$ 的人了的方案数。转移枚举这个人被放在了哪个区间即可:算出比这个人大且没用过的人的个数,组合数算一下就可以了(别忘了这是排列)
我们上面的计算是钦定了 $1$ 在 $1$ 位置的,注意到 $1$ 在其他的位置其实也是和这种情况等价的,所以答案要乘上个 $2^n$。

代码

/*
 * sto Qingyu orz
 * 感谢真神sqy无私的教诲。膜时队者处处阿克,只因大师sqy在他背后。不膜大师者违背了真神的旨意,真神必将降下天谴,
 * 使其天天爆零
 * 我不由自主地膜拜真神sqy。
 * Author: RainAir
 * Time: 2019-10-17 09:33:50
 */
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define P std::pair
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
#define int LL
const int MAXN = 16 + 1;
const int MAXM = 1e5 + 5;
const int ha = 1e9 + 7;
int f[MAXN+3][(1<<MAXN)+3];
int a[MAXN+3];
int fac[MAXM],inv[MAXM],pc[(1<<MAXN)+3];
int n,m;

inline int qpow(int a,int n=ha-2){
    int res = 1;
    while(n){
        if(n & 1) res = 1ll*res*a%ha;
        a = 1ll*a*a%ha;
        n >>= 1;
    }
    return res;
}

inline void prework(){
    fac[0] = 1;
    FOR(i,1,MAXM-1) fac[i] = 1ll*fac[i-1]*i%ha;
    inv[MAXM-1] = qpow(fac[MAXM-1]);
    ROF(i,MAXM-2,0) inv[i] = 1ll*inv[i+1]*(i+1)%ha;
}

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

signed main(){
    prework();
    scanf("%lld%lld",&n,&m);
    FOR(i,1,MAXM-1) pc[i] = pc[i>>1]+(i&1);
    FOR(i,1,m) scanf("%lld",a+i);
    std::sort(a+1,a+m+1);
    // f[i][S] 表示填到前 i 个数,S 区间最小值是这个数
    f[m+1][0] = 1;
    ROF(i,m,1){
        FOR(S,0,(1<<n)-1){
            (f[i][S] += f[i+1][S]) %= ha;
            int t = (1<<n)-S-a[i]; // 可以放的数
//            if(S == 0 && i == 1) DEBUG(t);
            FOR(j,0,n-1){
                if(S&(1<<j)) continue;
             //   if(S == 0 && i == 1) DEBUG(j),DEBUG((S|(1<<j))),DEBUG(t),DEBUG((1<<j)-1);
                (f[i][S|(1<<j)] += 1ll*f[i+1][S]*C(t,(1<<j)-1)%ha*fac[(1<<j)]%ha) %= ha;
            //    if(S == 0 && i == 1) DEBUG(f[i][S|(1<<j)]),DEBUG(f[1][1]);
            }
        }
    }
    int ans = 0;
    FOR(S,0,(1<<n)-1){
        (ans += (1ll*(pc[S]&1?ha-1:1)*f[1][S]%ha*fac[(1<<n)-S-1]%ha)) %= ha;
    }
    printf("%lld\n",1ll*ans*(1<<n)%ha);
    return 0;
}
Last modification:April 7th, 2020 at 10:14 pm
如果觉得我的文章对你有用,请随意赞赏