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

题面

有 \(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
    
     #include
     
      #include
      
       using namespace std;#define MOD 1000000007#define MAX 17inline 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<
       
        <
        
         <
         
          >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