标签:子集反演,动态规划
[ZJOI2016]小星星
题目描述
小 Y 是一个心灵手巧的女孩子，她喜欢手工制作一些小饰品。她有 \(n\) 颗小星星，用 \(m\) 条彩色的细线串了起来，每条细线连着两颗小星星。
有一天她发现，她的饰品被破坏了，很多细线都被拆掉了。这个饰品只剩下了 \(n-1\) 条细线，但通过这些细线，这颗小星星还是被串在一起，也就是这些小星星通过这些细线形成了树。小 Y 找到了这个饰品的设计图纸，她想知道现在饰品中的小星星对应着原来图纸上的哪些小星星。如果现在饰品中两颗小星星有细线相连，那么要求对应的小星星原来的图纸上也有细线相连。小 Y 想知道有多少种可能的对应方式。
对于 \(100\%\) 的数据，\(n\leq 17\)，\(m\leq \frac 12n(n-1)\)。
思路点拨
在这之前,你需要知道子集反演的一种形式.我们定义 \(f(S)\) 表示集合刚好为 \(S\) 的答案; \(g(S)\) 表示 \(S\) 的所有子集的答案之和.如果 \(g(A)=\sum_{B\subseteq A} f(B)\) ,那么
\[f(A)=\sum_{B\subseteq A} (-1) ^{|A|-|B|}g(B) \]回到这道题目,由于给树上节点编号的限制是一个排列,这不好解,所以我们可以子集反演变成可以给树上节点随便编号,只要使用地编号在集合 \(S\) 内就可以了.那么我们先枚举集合 \(S\) ,剩下的部分交给树形dp .
我们定义状态 \(f_{i,j}\) 表示在节点 \(i\) 的子树内, \(i\) 的编号是 \(j\) 的方案数.那么考虑转移,我们枚举 \(i\) 的儿子节点以及儿子节点的编号 \(k\) ,如果 \(j,k\) 之间有连边,就可以转移.写成公式就是:
\[f_{i,j}=\prod_{v \in son}\sum_{k=1}^{n} f_{v,k}[k \in S][j,k在图上有连边] \]容易看出这是 \(O(n^3)\) 的.
时空复杂度计算:时间 \(O(2^n n^3)\) ,空间 \(O(n^3)\) .
\(code\)
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-f;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
const int MAXN=18;
int n,m;
bool vis[MAXN][MAXN];
vector<int> e[MAXN];
int f[MAXN][MAXN];
int s[MAXN],top;
void dfs(int x,int dad){
for(int i=1;i<=top;i++)
f[x][s[i]]=1;
for(int i=0;i<e[x].size();i++){
int to=e[x][i];
if(to==dad) continue;
dfs(to,x);
for(int i=1;i<=top;i++){
int cnt=0;
for(int j=1;j<=top;j++)
if(vis[s[i]][s[j]])
cnt+=f[to][s[j]];
f[x][s[i]]*=cnt;
}
}
}
signed main(){
n=read(),m=read();
for(int i=1;i<=m;i++){
int u=read(),v=read();
vis[u][v]=vis[v][u]=1;
}
for(int i=1;i<n;i++){
int u=read(),v=read();
e[u].push_back(v);
e[v].push_back(u);
}
int ans=0;
for(int i=1;i<(1<<n);i++){
memset(f,0,sizeof(f));
top=0;
for(int j=0;j<n;j++)
if(i&(1<<j))
s[++top]=j+1;
dfs(1,-1);
int cnt=0;
for(int i=1;i<=top;i++)
cnt+=f[1][s[i]];
if((n-top)&1) ans-=cnt;
else ans+=cnt;
}
cout<<ans;
return 0;
}