AT3981 [ARC093D] Dark Horse

题解

你考虑首先固定 (1) 的位置，然后将答案乘上 (2^n) 即可，原因后面会说。

我们发现无论 (1) 在什么地方，跟他对战的一定是若干深度为 (i) 的子树的胜出者，而胜出者一定是其中数值最小的一个。

所以相当于是问我们将所有数分成若干组，第 (i) 组满足其中的数有 (2^{i-1}) 个且每组种数的顺序有区分，同时每组中最小的数不在 (a_i) 中，有多少种方案。

首先这个组数必然是有 (n) 组的，我们可以考虑倒序加入，用容斥计算有多少方案。

用 (f_{i,j}) 表示考虑到第 (i) 个限制同时 (j) 集合中的组已经填满，那么对于这种情况，剩下的如果随便填就是至少 (i) 个的情况了，你就直接利用这个容斥即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=20;
const int MOD=1e9+7;
int n,m,a[N];
int frac[1<<N],ifrac[1<<N];
int f[(1<<N)][N],res=0;
int ksm(int x,int k){
	int res=1;
	for(;k;k>>=1,x=x*x%MOD)
	if(k&1) res=res*x%MOD;
	return res;
}
int cal(int n,int m){
	if(n<m||n<0||m<0) return 0;
	return frac[n]*ifrac[m]%MOD*ifrac[n-m]%MOD;
}
bool cmp(int a,int b){return a>b;}
signed main(){
	cin>>n>>m;
	frac[0]=1;
	for(int i=1;i<=(1<<n);++i) frac[i]=frac[i-1]*i%MOD;
	ifrac[1<<n]=ksm(frac[1<<n],MOD-2);
	for(int i=(1<<n);i>=1;--i) ifrac[i-1]=ifrac[i]*i%MOD;
	for(int i=1;i<=m;++i) scanf("%lld",&a[i]);
	sort(a+1,a+1+m,cmp);
	f[0][0]=1;
	for(int i=0;i<(1<<n);++i){
		for(int j=1;j<=m;++j) f[i][j]+=f[i][j-1],f[i][j]%=MOD;
		for(int j=1;j<=n;++j){
			if(i&(1<<(j-1))) continue;
			for(int k=1;k<=m;++k){
				f[i|(1<<(j-1))][k]+=f[i][k-1]*cal((1<<n)-a[k]-i,(1ll<<(j-1))-1)%MOD*frac[1ll<<(j-1)]%MOD;
				f[i|(1<<(j-1))][k]%=MOD;
			}
		}
	}
	for(int i=0;i<(1<<n);++i){
		int cnt=0;
		for(int j=i;j;j-=(j&(-j)),cnt++);
		res+=ksm(MOD-1,cnt&1)*f[i][m]%MOD*frac[(1<<n)-i-1]%MOD;
		res%=MOD;
	}
	return printf("%lld
",res*(1<<n)%MOD),0;
}