【容斥原理】(AtCoder Regular Contest 093 F) Dark Horse

题意：

有$2^N$个选手参与一场比赛，比赛规则是：相邻的两个人比赛一次，败者淘汰掉，胜者继续进行，直到只剩一个人为止。
现在给出1号选手会败给哪些选手（实力摸得很清楚啊）
并且已知其他选手之间均满足：两个选手比赛，编号小的一定会胜利。
现在可以安排每个选手初始的位置，要 钦定 1号选手 Chicken Dinner 最后获胜，求能满足条件的初始位置的方案数。

---

分析：

首先，如果1号选手要胜利到最后，那么它一定会打N场比赛。
我们可以用一个图表来表示它的比赛过程：

可以看出，它首先与1个人比赛，再与两个人的编号最小的比赛，再与4个人的编号最小的比赛。并且，我们发现，无论他在哪个位置，都一定是按照这样的顺序（先与1个人，再与两人最小值……）
所以，我们可以令其在1号位置。得到方案后，再乘上$2^N$即可

现在，我们可以将与其比赛的人的区间再简化一点：
令$G_i$表示站i号位置的选手
那么$G_1$一定会与
$G_2,min\{G_3,G_4\},min\{G_5,G_6,G_7,G_8\}……min\{G_{2^{N-1}+1},G_{2^{N-1}+2},……,G_{2^N}\}$比赛

这样一来，我们只需要使得每一个块内的最小值都不在A的范围内即可。

接下来就是本题最有趣的地方了：容斥原理。
设S为N个块的一个子集，$f(S)$表示这个子集中所有块的最小值均在A的范围内（其余块是否在A的范围内不考虑）的方案数。

这样一来，最终答案即为$\sum(-1)^{|S|}f(S)$

现在证明一下：
首先，根据定义：$f(0)$代表了全部情况，
对任意一个我们要减去的方案来说（即至少存在一个块的最小值在A范围内），设其为$S_1$
对任意一个$S'\subseteq S_1$，$f(S')$都会将$S_1$这个方案计算进去，我们加上其最终权值，就能得到$S_1$最终的贡献。
那么其最终的贡献为：
$-C_{|S|}^1+C_{|S|}^2-C_{|S|}^3……C_{|S|}^{|S|}=-1$
如果你这个都证明不来。。那我只能推荐你多学学数论了
我还是写写吧：

$$C_{n}^0+C_{n}^2+C_{n}^4+……$$
$$=C_{n-1}^0+C_{n-1}^1+C_{n-1}^2+……+C_{n-1}^{n-1}$$
$$=C_n^1+C_n^3+C_n^5+……$$
所以
$$C_{n}^0+C_n^2+C_n^4+……-C_n^1-C_n^3-C_n^5-……=0$$
所以
$$-C_{n}^0=-C_n^1+C_n^2-C_n^3……=-1$$

是不是觉得容斥原理很妙？
再来看$f(S)$怎么求：由于其余部分不考虑，我们只需要考虑哪些块的最小值必须在A中即可。

那么我们将A从大到小排序，依次考虑加入$A_i$后的$f(S)$。
1、成为一个块的最小值：那么在这个块中，必须填充相应数量的，编号比$A_i$大的选手，组合数统计。
2、不成为块的最小值，不操作即可$（dp[i][S]+=dp[i-1][S]）$。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define SF scanf
#define PF printf
#define MAXN 65636
#define MAXM 20
#define MOD 1000000007
using namespace std;
long long dp[2][MAXN],q[MAXN],p[MAXN];
int a[MAXM],n,m;
bool cmp(int x,int y){return x>y;
}
long long fsp(long long x,int y){long long res=1;while(y){if(y&1)res=(res*x)%MOD;x=(x*x)%MOD;y>>=1;}return res;
}
long long C(int x,int y){if(x<y)return 0;return ((q[x]*p[y])%MOD*p[x-y])%MOD;
}
int count(int x){int res=0;while(x){if(x&1)res++;x>>=1;}return res%2;
}
int main(){SF("%d%d",&n,&m);for(int i=1;i<=m;i++)SF("%d",&a[i]);q[0]=1;for(int i=1;i<(1<<n);i++)q[i]=(1ll*q[i-1]*i)%MOD;p[(1<<n)-1]=fsp(q[(1<<n)-1],MOD-2);for(int i=(1<<n)-1;i>=1;i--)p[i-1]=(1ll*p[i]*i)%MOD;sort(a+1,a+1+m,cmp);int now=0;dp[now][0]=1;for(int i=1;i<=m;i++){now^=1;for(int j=0;j<(1<<n);j++){if(dp[now^1][j]==0)continue;dp[now][j]=(dp[now][j]+dp[now^1][j])%MOD;int les=(1<<n)-1-j;for(int k=0;k<n;k++)if((j&(1<<k))==0){dp[now][j|(1<<k)]+=((C(les-a[i]+1,(1<<k)-1)*dp[now^1][j])%MOD*q[1<<k])%MOD;dp[now][j|(1<<k)]%=MOD;}}memset(dp[now^1],0,sizeof dp[now^1]);}long long ans=0;for(int i=0;i<(1<<n);i++){if(dp[now][i]==0)continue;dp[now][i]=(dp[now][i]*q[(1<<n)-1-i])%MOD;if(count(i)==0)ans+=dp[now][i];elseans-=dp[now][i];ans%=MOD;}ans<<=n;ans%=MOD;PF("%lld",(ans+MOD)%MOD);
}