[ARC093-F][容斥原理][DP]Dark Horse

Description

题解

比赛过程可以看成一棵满的二叉树
不妨把第一个人先固定在1的位置上，答案乘一个$2^n$就行了
因为显然相同子树内对调一下两个儿子没有影响
于是就是1先和2比，再和min(3~4),min(5~8),min(9~16)…这些比
那显然这m个数不能是任意一个区间的最小值
直接做不好做，容斥一下
这个容斥还是很常规的…
先把这m个数从大到小排
设一个$dp[i][mask]$表示前i个数确定了$mask$这个状态的区间的最小值
转移直接转移就行了…

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
using namespace std;
inline LL read()
{
    LL f=1,x=0;char ch=getchar();while(ch<'0'||ch>'9'){
    if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
    x=x*10+ch-'0';ch=getchar();}return x*f;
}
int stack[20];
inline void write(int x)
{
    if(x<0){
    putchar('-');x=-x;}if(!x){
    putchar('0');return;}int top=0;while(x)stack[++top]=x%10,x/=10;while(top)putchar(stack[top--]+'0');
}
inline void pr1(int x){
    write(x);putchar(' ');}
inline void pr2(int x){
    write(x);putchar('\n');}
const int MAXN=1000005;
const int MAXM=21;
const int MAXMASK=(1<<16);
const LL mod=1e9+7;
int bin[MAXM];
LL pre[MAXN],inv[MAXN];
LL pow_mod(LL a,LL b)
{
    LL ret=1;while(b){
    if(b&1)ret=ret*a%mod;a=a*a%mod;b>>=1;}return ret;
}
LL C(int n,int m){
    return pre[n]*inv[m]%mod*inv[n-m]%mod;}
int n,m,a[MAXM];
int f[MAXM][MAXMASK],ct[MAXMASK];
void ad(int &x,int y){
    x+=y;if(x>=mod)x-=mod;}
void dl(int &x,int y){
    x-=y;if(x<0)x+=mod;}
int main()
{
    pre[0]=1;for(int i=1;i<MAXN;i++)pre[i]=pre[i-1]*i%mod;inv[MAXN-1]=pow_mod(pre[MAXN-1],mod-2);for(int i=MAXN-2;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;bin[1]=1;for(int i=2;i<=20;i++)bin[i]=bin[i-1]<<1;for(int i=0;i<MAXMASK;i++)for(int j=1;j<=16;j++)if(i&bin[j])ct[i]+=bin[j];n=read();m=read();for(int i=1;i<=m;i++)a[i]=read();sort(a+1,a+1+m);reverse(a+1,a+1+m);f[0][0]=1;for(int i=1;i<=m;i++)for(int k=0;k<bin[n+1];k++){
    ad(f[i][k],f[i-1][k]);for(int j=1;j<=n;j++)if(!(k&bin[j])){
    if(bin[n+1]-a[i]+1-k>=bin[j])ad(f[i][k|bin[j]],(LL)f[i-1][k]*C(bin[n+1]-a[i]-k,bin[j]-1)%mod*pre[bin[j]]%mod);}}int ans=0;for(int i=0;i<bin[n+1];i++){
    int u1=(LL)f[m][i]*pre[bin[n+1]-i-1]%mod,u2=0;for(int j=1;j<=n;j++)if(i&bin[j])u2++;if(u2&1)dl(ans,u1);else ad(ans,u1);}ans=(LL)ans*bin[n+1]%mod;pr2(ans);return 0;
}