P3349 [ZJOI2016] 小星星 题解 - 容斥学习

前言

之前从来没学习过容斥模型，这次这个题作为我的第一个容斥例题学习。

正文

0x00 问题分析

这个问题可以抽象为：给定一个图 $G$ 和一棵树 $Tree$ 要求对于树重新编号，编号是一个 $n$ 的排列，假如树上任意一个父亲编号为 $x$ 任意其儿子的编号为 $y$ 则需要满足在图 $G$ 上有编号为 $x$ 和 $y$ 的连边。

显然有一个状压 dp ，即定义 $dp_{i,x,S}$ 为树上原本标号为 $i$ 的节点被标号为 $x$ ，并且其子树使用了 $S$ 这个集合中的编号。这样直接计算时间复杂度为 $\mathcal{O}\left(n^33^n\right)$ 这样会直接 T 掉考虑优化。

可以发现时间复杂度卡在要考虑 $S$ 这个限制。那么考虑去除 $S$ 一维，直接跑多次 dp 每次限定一个可用于编号的集合 $S$ 。但是这样就没有限制了，并没有办法保证排列了，但是可以保证边的限制合法。但是这样是典型的交容斥，如何理解呢？

考虑每一个解(不管是否是排列，只需要这个解边的限制合法)作为元素(这个元素是一个集合就是标号的一个子集，即 $S$ )设所有解的集合为 $U$ ，将这个解的 $S$ 中的点作为其属性，我们要求的就是每一个含有这个属性(即编号)的集合 $T$ ，设包含 $i$ 这个编号属性的元素集合为 $T_i$ 。要求的就是所有 $T$ 的交。

0x01 容斥推导

根据容斥公式有：

$$\left|\bigcap_{i=1}^{n}T_i\right|=\left|U\right|-\left|\bigcup_{i=1}^{n}\overline{T_i}\right|$$

且对于任意集合 $P_i$ 有：

$$\left|\bigcup_{i=1}^{n}P_i\right|=\sum_{m=1}^n\left(-1\right)^{m-1}\sum_{a_i<a_{i+1}}\left|\bigcup_{i=1}^{m}P_{a_i}\right|$$

即

$$\left|\bigcup_{i=1}^{n}\overline{T_i}\right|=\sum_{m=1}^n\left(-1\right)^{m-1}\sum_{a_i<a_{i+1}}\left|\bigcap_{i=1}^{m}\overline{T_{a_i}}\right|$$

实际上 $\left|U\right|$ 就是可以用任意标号去标。

而对于

$$\sum_{a_i<a_{i+1}}\left|\bigcap_{i=1}^{m}\overline{T_{a_i}}\right|$$

相当于在任意选了 $m$ 个点不选的解的数量。发现这个统计是容易的即 $\left|S\right|=n-m$ 时的解的数量。

记 $Cnt_i$ 表示 $\left|S\right|=i$ 时的解的数量，最终得到了：

$Ans=Cnt_n-Cnt_{n-1}+Cnt_{n-2}\cdots$

0x02 DP细化

现在可以放心的 DP 了，假设当前钦定可用于标号的点集为 $S$ ，有：

$$Dp_{u,x}=\prod_{y\in S} \sum_{v\in son_u} Dp_{u,y}\times\left[G_{x,y}\right]$$

其中 $\left[G_{x,y}\right]$ 表示在图 $G$ 上是否有边 $\left(x,y\right)$ 。

DFS DP 即可

0x03 代码实现

AC CODE

#include<bits/stdc++.h>
// #define ONLINE_JUDGE
#define INPUT_DATA_TYPE int
#define OUTPUT_DATA_TYPE long long
INPUT_DATA_TYPE read(){register INPUT_DATA_TYPE x=0;register char f=0,c=getchar();while(c<'0'||'9'<c)f=(c=='-'),c=getchar();while('0'<=c&&c<='9')x=(x<<3)+(x<<1)+(c&15),c=getchar();return f?-x:x;}void print(OUTPUT_DATA_TYPE x){register char s[20];register int i=0;if(x<0){x=-x;putchar('-');}if(x==0){putchar('0');return;}while(x){s[i++]=x%10;x/=10;}while(i){putchar(s[--i]+'0');}return;}

int n,m;
long long f[20][20];

std::vector<int> tree[20],scur;
std::bitset<20> graph[20];

void addEdge_tree(int u,int v){tree[u].push_back(v);tree[v].push_back(u);return;}
void addEdge_graph(int u,int v){graph[u][v]=graph[v][u]=1;return;}

void dfs(int u,int p){
	for(auto v:tree[u])
		if(v!=p)
			dfs(v,u);
	register long long sum;
	for(auto x:scur){
		f[u][x]=1;
		for(auto v:tree[u]){
			if(v==p) continue;
			sum=0;
			for(auto y:scur)
				sum+=f[v][y]*graph[x][y];
			f[u][x]*=sum;
		}
	}
	return;
}

int main(){
	#ifndef ONLINE_JUDGE
	freopen("name.in", "r", stdin);
	freopen("name.out", "w", stdout);
	#endif

    register int i,u,v,s,maxs;
	register long long ans=0;
    n=read();
    m=read();
	for(i=0;i<m;++i){
		u=read()-1;
		v=read()-1;
		addEdge_graph(u,v);
	}

	for(i=1;i<n;++i){
		u=read()-1;
		v=read()-1;
		addEdge_tree(u,v);
	}

	maxs=(1<<n);

	for(s=0;s<maxs;++s){
		scur.clear();
		for(i=0;i<n;++i)
			if((s>>i)&1) scur.push_back(i);
		dfs(0,0);
		if((n-scur.size())&1)
			for(auto id:scur)
				ans-=f[0][id];
		else
			for(auto id:scur)
				ans+=f[0][id];
	}

	print(ans);

	#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	#endif
    return 0;
}

总结

容斥的题首先要想到一个次优的解法，并且想要优化的过程中需要发现其符合容斥的性质才能完成。