Problem Statement
There are $2^N$ players, numbered $1, 2, ..., 2^N$. They decided to hold a tournament.
The tournament proceeds as follows:
- Choose a permutation of $1, 2, ..., 2^N$: $p_1, p_2, ..., p_{2^N}$.
- The players stand in a row in the order of Player $p_1$, Player $p_2$, $...$, Player $p_{2^N}$.
- Repeat the following until there is only one player remaining in the row:
- Play the following matches: the first player in the row versus the second player in the row, the third player versus the fourth player, and so on. The players who lose leave the row. The players who win stand in a row again, preserving the relative order of the players.
- The last player who remains in the row is the champion.
It is known that, the result of the match between two players can be written as follows, using $M$ integers $A_1, A_2, ..., A_M$ given as input:
- When $y = A_i$ for some $i$, the winner of the match between Player $1$ and Player $y$ ($2 \leq y \leq 2^N$) will be Player $y$.
- When $y \neq A_i$ for every $i$, the winner of the match between Player $1$ and Player $y$ ($2 \leq y \leq 2^N$) will be Player $1$.
- When $2 \leq x < y \leq 2^N$, the winner of the match between Player $x$ and Player $y$ will be Player $x$.
The champion of this tournament depends only on the permutation $p_1, p_2, ..., p_{2^N}$ chosen at the beginning. Find the number of permutation $p_1, p_2, ..., p_{2^N}$ chosen at the beginning of the tournament that would result in Player $1$ becoming the champion, modulo $10^9 + 7$.
Constraints
- $1 \leq N \leq 16$
- $0 \leq M \leq 16$
- $2 \leq A_i \leq 2^N$ ($1 \leq i \leq M$)
- $A_i < A_{i + 1}$ ($1 \leq i < M$)
容易发现， \(1\) 节点所在的位置不影响答案，强制 \(1\) 节点在最左边，跑出答案后乘上 \(2^n\) 就可以了
那么我们现在要求第 \([2,2],[3,4],[5,8]\cdots\) 的最小值都不在这 \(m\) 个数中的排列数。
我们难以计算这个答案，但是可以考虑容斥，计算出至少有 \(p\) 个能打败 \(1\) 的点成为最小值的情况数。
先考虑如果我们知道哪 \(i\) 个数分别是哪个区间的最小值，我们怎么求答案？ 把这些点按照 \(a\) 从大到小排序（其实也就是把个的序列反转），然后按顺序计算答案。如果在这个点填入之前已经有 \(p\) 个位置有值了，这个区间就有 \(2^n-a_i-1-p\) 个选法，算个排列数就好了。
那么真正去做的时候也一样，把 \(a\) 序列反转后，定义 \(dp_s\) 为还没有填入的区间集合为 \(s\)，有多少种方案。枚举这个 \(a_i\) 有填到那些区间，容斥 dp 就可以了。
#include<bits/stdc++.h>
using namespace std;
const int N=17,S=1<<N,P=1e9+7;
int n,m,f[S],iv[S],inv[S],dp[S],ans,a[N];
int C(int n,int m)
{
if(n<m)
return 0;
return 1LL*f[n]*iv[m]%P*iv[n-m]%P;
}
int main()
{
scanf("%d%d",&n,&m);
f[0]=f[1]=iv[0]=iv[1]=inv[1]=1;
for(int i=2;i<S;i++)
{
f[i]=1LL*f[i-1]*i%P;
inv[i]=(P-P/i)*1LL*inv[P%i]%P;
iv[i]=1LL*iv[i-1]*inv[i]%P;
}
for(int i=1;i<=m;i++)
scanf("%d",a+i);
reverse(a+1,a+m+1);
dp[(1<<n)-1]=1;
static const int T=(1<<n)-1;
for(int i=1,s=0;i<=m;i++)
{
for(int j=0;j<(1<<n);j++)
{
for(int k=0;k<n;k++)
{
if(j>>k&1)
continue;
int to=j^(1<<k);
(dp[j]+=(P-dp[to])*1LL*C((1<<n)-(T^to)-a[i],(1<<k)-1)%P*f[(1<<k)]%P)%=P;
}
}
}
for(int j=0;j<(1<<n);j++)
(ans+=dp[j]*1LL*f[j]%P)%=P;
printf("%lld",ans*1LL*(1<<n)%P);
return 0;
}