ARC 093 F Dark Horse 容斥状压dp 组合计数

LINK：Dark Horse

首先考虑1所在位置.

假设1所在位置在1号点对于此时剩下的其他点的方案来说.

把1移到另外一个点对于刚才的所有方案来说相对位置不变是另外的方案.

可以得到 1在任何位置剩下的方案数都相同所以不妨设1所在点为1 求出方案乘以n.

考虑怎么求方案即求出剩下的n-1个区间且每个区间的最小值都不能是给出的m的值.

直接做需要状压做不了。

考虑容斥容易想到答案为\(\sum_{s}(-1)^{|s|}f_s\)

其中\(f_s\)表示集合s一定不合法的方案数.

求这个东西也很麻烦. 对于那m个人显然要排序.

从小到大dp 可以发现大的可以放到小的位置至此还需要再记一个状压状态直接炸了.

考虑从大到小dp 此时可以发现钦定大的为最小值小的就不能再放到大的里面了然后就可以dp了.

推出式子后可以发现可以前缀和优化一下复杂度\(n\cdot m\cdot 2^n\)

code

//#include<bits/stdc++.h>

#include<iostream>

#include<cstdio>

#include<ctime>

#include<cctype>

#include<queue>

#include<deque>

#include<stack>

#include<iostream>

#include<iomanip>

#include<cstdio>

#include<cstring>

#include<string>

#include<ctime>

#include<cmath>

#include<cctype>

#include<cstdlib>

#include<queue>

#include<deque>

#include<stack>

#include<vector>

#include<algorithm>

#include<utility>

#include<bitset>

#include<set>

#include<map>

#define ll long long

#define db double

#define INF 10000000000000000ll

#define inf 1000000000

#define ldb long double

#define pb push_back

#define put_(x) printf("%d ",x);

#define get(x) x=read()

#define gt(x) scanf("%d",&x)

#define gi(x) scanf("%lf",&x)

#define put(x) printf("%d\n",x)

#define putl(x) printf("%lld\n",x)

#define rep(p,n,i) for(RE int i=p;i<=n;++i)

#define go(x) for(int i=lin[x],tn=ver[i];i;tn=ver[i=nex[i]])

#define fep(n,p,i) for(RE int i=n;i>=p;--i)

#define vep(p,n,i) for(RE int i=p;i<n;++i)

#define pii pair<int,int>

#define mk make_pair

#define RE register

#define gf(x) scanf("%lf",&x)

#define pf(x) ((x)*(x))

#define uint unsigned long long

#define ui unsigned

#define EPS 1e-4

#define sq sqrt

#define S second

#define F first

#define mod 1000000007

using namespace std;

char *fs,*ft,buf[1<<15];

inline char gc()

{

	return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;

}

inline int read()

{

	RE int x=0,f=1;RE char ch=gc();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=gc();}

	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=gc();}

	return x*f;

}

const int MAXN=18,maxn=1<<MAXN;

int n,m,maxx;

int a[MAXN],f[MAXN][maxn],g[maxn];

int c[maxn],fac[maxn],inv[maxn];

inline int ksm(int b,int p)

{

	int cnt=1;

	while(p)

	{

		if(p&1)cnt=(ll)cnt*b%mod;

		b=(ll)b*b%mod;p=p>>1;

	}

	return cnt;

}

inline int C(int a,int b){return a<b?0:fac[a]*(ll)inv[b]%mod*inv[a-b]%mod;}

int main()

{

	//freopen("1.in","r",stdin);

	get(n);get(m);

	rep(1,m,i)get(a[i])-1;

	sort(a+1,a+1+m);

	reverse(a+1,a+1+m);

	maxx=1<<n;--maxx;

	fac[0]=1;

	rep(1,maxx,i)fac[i]=(ll)fac[i-1]*i%mod;

	inv[maxx]=ksm(fac[maxx],mod-2);

	fep(maxx-1,0,i)inv[i]=(ll)inv[i+1]*(i+1)%mod;

	f[0][0]=1;

	rep(1,m,i)

	{

		fep(maxx,0,j)

		{

			f[i][j]=f[i-1][j];

			if(!f[i-1][j])continue;

			rep(1,n,k)

			{

				if(1<<(k-1)&j)continue;

				f[i][j|1<<(k-1)]=(f[i][j|1<<(k-1)]+(ll)f[i-1][j]*C(maxx-a[i]-j,(1<<(k-1))-1)%mod*fac[(1<<(k-1))])%mod;

			}

		}

	}

	int ans=0;

	rep(0,maxx,i)

	{

		g[i]=g[i>>1]+(i&1);

		ans=(ans+(g[i]&1?-1:1)*(ll)f[m][i]*fac[maxx-i])%mod;

	}

	ans=(ll)ans*(maxx+1)%mod;

	ans=(ans+mod)%mod;put(ans);

	return 0;

}

巴特西

ARC 093 F Dark Horse 容斥状压dp 组合计数

最新文章

热门文章

巴特西

ARC 093 F Dark Horse 容斥 状压dp 组合计数

最新文章

热门文章

ARC 093 F Dark Horse 容斥状压dp 组合计数