【arc093f】Dark Horse（容斥原理，动态规划，状态压缩）

题面

atcoder
有 (2^n) 名选手，编号为 (1) 至 (2^n) 。现在这 (2^n) 名选手将进行 (n) 轮淘汰赛，决出胜者。若 (x<y) ，则 (x) 能够战胜 (y) 。但有 (m) 个例外，(1) 号选手会输给这 (m) 个选手。问有多少中排列方式使得(1)号选手取得胜利。(n,m≤16)。
（这是肖大佬的翻译）

题解

钦定(1)号站在一号位置（这个无所谓吧），剩下的第(i)个位置站的人是(p_i)，那么首先(1)会和(p_2)打，然后和(min(p_3,p_4))，接下来是(min(p_5,p_6,p_7,p_8))，以此类推下去。
我们的方案数等于上述(n)个集合中每个集合的最小值都不是给定的(m)个人。
直接算不好搞，容斥考虑。钦定哪些块的最小值一定是给定的(m)个人，那么假设给这(n)个区间的人，也就是把这(n)块编号然后状压一下，那么方案数定义为(f(S))，那么最终的答案就是(sum (-1)^{|S|}f(S))。

至于这个(f(S))怎么求？我们把所有数从大往小排序，考虑(dp)，设(f[i][S])表示最大的(i)个标号的人中，(S)所代表的子集所包含的区间中的最小值是给定的(m)个人中的一个。转移的话首先是这个人不放入任何一个集合中。另外是构成一个集合的最小值，枚举一下构成哪个集合，然后用组合数算一下方案数即可。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define MOD 1000000007
#define MAX 17
inline int read()
{
	int x=0;bool t=false;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if(ch=='-')t=true,ch=getchar();
	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
	return t?-x:x;
}
void add(int &x,int y){x+=y;if(x>=MOD)x-=MOD;}
int bin[MAX],jc[1<<MAX],inv[1<<MAX],jv[1<<MAX];
int C(int n,int m){if(n<m)return 0;return 1ll*jc[n]*jv[m]%MOD*jv[n-m]%MOD;}
int a[MAX],n,m,ans,f[MAX+1][1<<MAX],cnt[1<<MAX];
int main()
{
	n=read();m=read();cnt[0]=jc[0]=bin[0]=jv[0]=inv[0]=inv[1]=1;
	for(int i=1;i<=n;++i)bin[i]=bin[i-1]<<1;
	for(int i=1;i<=bin[n];++i)jc[i]=1ll*jc[i-1]*i%MOD;
	for(int i=2;i<=bin[n];++i)inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD;
	for(int i=1;i<=bin[n];++i)jv[i]=1ll*jv[i-1]*inv[i]%MOD;
	for(int i=1;i<=bin[n];++i)cnt[i]=(i&1)?MOD-cnt[i>>1]:cnt[i>>1];
	for(int i=1;i<=m;++i)a[i]=read();sort(&a[1],&a[m+1]);
	f[m+1][0]=1;
	for(int i=m;i;--i)
		for(int t=0;t<bin[n];++t)
			if(f[i+1][t])
			{
				add(f[i][t],f[i+1][t]);
				int p=bin[n]-1-t;
				for(int j=0;j<n;++j)
					if(!(t&(1<<j)))
						add(f[i][t|(1<<j)],1ll*C(p-a[i]+1,(1<<j)-1)*f[i+1][t]%MOD*jc[1<<j]%MOD);
			}
	for(int i=0;i<bin[n];++i)
		add(ans,1ll*f[1][i]*jc[bin[n]-1-i]%MOD*cnt[i]%MOD);
	ans=1ll*ans*bin[n]%MOD;
	printf("%d
",ans);
	return 0;
}