画一个线段树撕烤一下,容易发现,\(1\) 号点要战胜的应该是若干个区间标号最小的点。

而且不管 \(1\) 在哪里,都是 \(n\) 个区间,大小分别为 \(2^0,2^1,2^2,...,2^{n-1}\) ,每次答案是一样的,最后乘 \(2^n\) 即可。

也就是求把 \(2\)\(2^n\) 分到 \(n\) 个集合,满足每个集合的最小标号不在给出的集合 \(A\) 中。

容斥吧… \(DP\) 求方案数,\(f(i,S)\) 表示考虑从大到小考虑到 \(A_i\)\(S\) 这些的集合被装好,且最小标号在 \(A\)

\(A_i\) 从大到小,转移很方便。答案就是 \(\sum_{S} (-1)^{|S|}f(m,S)(2^n-1-sum(S)\ )!\)

\(sort\) 从大到小是 \(greater\)mmp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int P=1e9+7,maxn=(1<<16)+5;
int n,m,a[20];
LL f[20][maxn],fac[maxn],inv[maxn],fac_inv[maxn],ans;
LL C(int n,int m){
if(n<0||m<0||n<m) return 0;
return fac[n]*fac_inv[m]%P*fac_inv[n-m]%P;
}
int main(){
freopen("arc093_d.in","r",stdin);
freopen("arc093_d.out","w",stdout);
scanf("%d%d",&n,&m);
fac[0]=1; for(int i=1;i<=(1<<n);i++) fac[i]=fac[i-1]*i%P;
inv[1]=1; for(int i=2;i<=(1<<n);i++) inv[i]=(LL)(P-P/i)*inv[P%i]%P;
fac_inv[0]=1; for(int i=1;i<=(1<<n);i++) fac_inv[i]=fac_inv[i-1]*inv[i]%P;
for(int i=1;i<=m;i++) scanf("%d",&a[i]);
sort(a+1,a+1+m,greater<int>());
f[0][0]=1;
for(int i=0;i<=m-1;i++)
for(int s=0;s<=(1<<n)-1;s++)
if(f[i][s]){
(f[i+1][s]+=f[i][s])%=P;
for(int j=0;j<=n-1;j++)
if(!((s>>j)&1))
(f[i+1][s|(1<<j)]+=f[i][s]*C((1<<n)-a[i+1]-s,(1<<j)-1)%P*fac[1<<j]%P)%=P;
}
for(int s=0;s<=(1<<n)-1;s++){
int sz=0; for(int i=0;i<=n-1;i++) if((s>>i)&1) sz++;
ans=(ans+f[m][s]*fac[(1<<n)-1-s]*((sz&1)?-1:1))%P;
}
printf("%d\n",(ans*(1<<n)%P+P)%P);
return 0;
}