组合计数Ⅰ

—— from nfls 2025 summer camp

T1 [ZJOI2016] 小星星

link
思路
首先看到 $n\le 17$ 以及计数 可以想到排列组合，DP ，容斥之类的东西。
考虑状压。设 $f_{i,j,s}$ 表示树上的结点 $i$ 映射到原图上为 $j$ 且 $i$ 子树内的点全部映射到图上的集合为 $s$ 的合法方案数。转移就是 树形DP 。时间复杂度为 $O(n^3\times 3^n)$ 。发现复杂度瓶颈在于枚举集合子集。考虑压缩状态，将 $s$ 这一维压缩，这个时候会出现有重复的编号，发现是可以容斥掉的。
枚举整棵树映射到图上的编号集合（允许编号重复），那么答案就是 |s|=n 的方案 - |s|=n-1 的方案 + |s=n-2| 的方案 - ... 。复杂度降为 $O(n^3\times 2^n)$ 。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=20;

int idx,head[maxn];
struct EDGE{ int v,next; }e[maxn*2];
void Insert(int u,int v){
	e[++idx]={v,head[u]};
	head[u]=idx;
}

int n,a[maxn],cnt;
ll f[maxn][maxn];
bool gp[maxn][maxn];
void Dfs(int x,int fa){
	for(int i=1;i<=n;i++)
		f[x][i]=0;
	for(int i=head[x];i;i=e[i].next){
		int v=e[i].v;
		if(v!=fa) Dfs(v,x);
	}
	for(int i=1;i<=cnt;i++){
		f[x][a[i]]=1;
		for(int j=head[x];j;j=e[j].next){
			int v=e[j].v;
			if(v!=fa){
				ll s=0;
				for(int k=1;k<=cnt;k++)
					if(gp[a[i]][a[k]]) s+=f[v][a[k]];
				f[x][a[i]]*=s;
			}
		}
	}
}

int main(){
	int m; cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y; cin>>x>>y;
		gp[x][y]=gp[y][x]=1;
	} 
	for(int i=1;i<n;i++){
		int x,y; cin>>x>>y;
		Insert(x,y),Insert(y,x);
	}
	ll ans=0;
	for(int i=1,S=(1<<n);i<S;i++){
		cnt=0;
		for(int j=1;j<=n;j++)
			if((1<<(j-1))&i) a[++cnt]=j;
		Dfs(1,0);
		ll s=0;
		for(int j=1;j<=cnt;j++)
			s+=f[1][a[j]];
		if((n-cnt)&1) ans-=s;
		else ans+=s;
	}
	cout<<ans;
	return 0;
}