BZOJ 4455: [Zjoi2016]小星星(容斥+树形dp)

解题思路

　　首先题目中有两个限制，第一个是两个集合直接必须一一映射，第二个是重新标号后，\(B\)中两点有边\(A\)中也必须有。发现限制\(2\)比较容易满足，考虑化简限制\(1\)。令\(f(S)\)表示重标号后至多出现在\(S\)中的标号且满足条件\(2\)的方案数，令\(g(S)\)表示重标号后恰好出现在\(S\)中的标号满足条件\(2\)的方案数。这应该是容斥里的一个套路。那么有转移方程：

\[f(S)=\sum\limits_{T \subseteq S}g(T)\Rightarrow g(S)=\sum\limits_{T \subseteq S}(-1)^{\left|S\right |-\left|T\right|}f(T)
\]

　　然后问题就转化成为求\(f(S)\)了。令\(h[i][j]\)表示\(i\)点重新标号后是\(j\)的方案数。那么转移的时候考虑\(x\)的儿子\(u\)产生的贡献，可以枚举\(u\)的重标号，然后看他们两个的重标号之间有没有边，如果有的话\(cnt+=h[u][j]\)，最后\(u\)对\(h[i][j]\)的贡献就为\(cnt\)。时间复杂度\(O(2^n*n^3)\)，在下人丑常数大，\(bzoj\)卡了半天才过。。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<cstdlib>

using namespace std;

const int MAXN = 18;

typedef long long LL;

inline int rd(){

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

	while(!isdigit(ch)) f=ch=='-'?0:1,ch=getchar();

	while(isdigit(ch))  x=(x<<1)+(x<<3)+ch-'0',ch=getchar();

	return f?x:-x;

}

int n,m,head[MAXN],cnt,a[MAXN][MAXN],zz[MAXN];

int to[MAXN<<1],nxt[MAXN<<1],tot;

LL g[MAXN][MAXN],ans,now;

bool use[MAXN];

void out(LL x){

	if(!x) return ;

	out(x/10);putchar('0'+x%10);

}

inline void add(int bg,int ed){

	to[++cnt]=ed,nxt[cnt]=head[bg],head[bg]=cnt;

}

void dfs(int x,int f){

	int u;LL sum;

	for(register int i=1;i<=tot;i++) g[x][i]=1;

	for(register int i=head[x];i;i=nxt[i]){

		u=to[i];if(u==f) continue;dfs(u,x);

		for(register int j=1;j<=tot;j++){sum=0;

			for(register int k=1;k<=tot;k++)

				if(a[zz[j]][zz[k]]) sum+=g[u][k];

			g[x][j]*=sum;

		}

	}

}

int main(){

	n=rd(),m=rd();int x,y;

	for(register int i=1;i<=m;i++){

		x=rd(),y=rd();

		a[x][y]=a[y][x]=1;

	}

	for(register int i=1;i<n;i++){

		x=rd(),y=rd();

		add(x,y),add(y,x);

	}int num;

	for(register int S=1;S<1<<n;S++){

		tot=0;num=0;now=0;

		for(register int i=1,T=S;T;T>>=1,i++)

			if(T&1) num++,zz[++tot]=i;

		num=n-num;dfs(1,0);for(register int i=1;i<=tot;i++) now+=g[1][i];

		if(num&1) ans-=now;else ans+=now;

	}

	if(!ans) putchar('0');else out(ans);

	return 0;

}

巴特西

BZOJ 4455: [Zjoi2016]小星星(容斥+树形dp)

解题思路

代码

最新文章

热门文章