标签：mathbb exists 小星星 反演 子集 ZJOI2016 forall 转移

前言

大风天踢了会球, 立竿见影就觉得感冒了, 无敌了, 一会去医务室整点抗病毒

颓了一会好点了()

思路

首先转化题意

给你一张 \(n\) 点 \(m\) 边的图 \(\mathbb{G}\) 和一棵同样由这 \(n\) 个点组成的树 \(\mathbb{T}\), 求对树上的点有多少中标号方式 \(p\), 使得 \(\forall {(u, v)} \in \mathbb{T} , \exists (p_u, p_v) \in \mathbb{G}\)

又是数数, 怎么做呢
你注意到 \(n \leq 17\) , 明示了状压, 我们考虑往这个方向想

考虑树形 \(\rm{dp}\) , 令 \(f_{i, \mathbb{S}}\) 表示 \(i\) 的子树中映射了原图中 \(\mathbb{S}\) 中的点的方案数, 也就是说这些编号已经被使用
考虑转移, 你发现对于 \(f_{i, \mathbb{S}}\) , 我们需要找到 \(\mathbb{S}\) 的一些不相交子集, 而且要确定 \(\forall j \in son(i) , \exists (p_i, p_j) \in \mathbb{G}\) , 你发现仅仅靠当前的状态, 不能确定 \(\forall j \in son(i) , \exists (p_i, p_j) \in \mathbb{G}\) 的条件, 所以考虑加一维

令 \(f_{i, j, \mathbb{S}}\) 表示对于 \(i\) 子树, 将 \(i\) 映射到 \(j\) , 子树中已经映射的点集为 \(\mathbb{S}\) , 可能的方案数
考虑转移, 我们可以通过将子树一个一个插入来转移

\[\forall u \in son(i) , f_{i, j, \mathbb{S} \cup \mathbb{S}^{\prime}} \stackrel {\exists (j, v) \in \mathbb{G}, \mathbb{S} \cap \mathbb{S}^{\prime} = \varnothing} {\longleftarrow} f_{u, v, \mathbb{S}} \cdot f_{i, j, \mathbb{S}^{\prime}} \]

首先要对这样转移的正确性打个补丁
很容易发现的问题是, 残留了一些非法的状态, 例如 \(f_{i, j, \mathbb{S}}\) 这样一个状态, 其子树有可能并没有填充完
很好想到的处理方法是, 对于所有状态, 只有 \(|\mathbb{S}| = siz_i\) 的才有意义, 对于其他的情况, 用完即弃即可

你发现这样子做的时间复杂度是 \(\mathcal{O} (n^3 3^n)\) , 过不去
科技优化到 \(\mathcal{O} (n^4 2^n)\) ,过不去

只能从本质上进行优化

---

看了下 \(\rm{TJ}\) , 发现新大陆「子集反演」, 直觉告诉我其与「选择」类问题有关联

子集反演的一些基础知识 不在赘述

考虑令 \(f(\mathbb{S})\) 表示「至多」选择 \(\mathbb{S}\) 中的点集进行编号, \(g(\mathbb{S})\) 表示「恰好」选择 \(\mathbb{S}\) 中的点集进行编号, 套路转移

一个误区是我们必须确保 \(g(\mathbb{S})\) 计算的是至少用一次, 而 \(f\) 没有这个要求, 容易发现

\[f(\mathbb{S}) = \sum_{\mathbb{T} \subseteq \mathbb{S}} g(\mathbb{T}) \]

因为是枚举集合, 所以当然也就没有组合数, 也就当然没有二项式反演的广泛性

余下的都是套路

总结

神秘的转移方式, 拆分集合的新 \(\rm{trick}\)

「子集反演」解决的一类特殊问题, 常常用于优化状态压缩类的问题

标签：mathbb,exists,小星星,反演,子集,ZJOI2016,forall,转移
From： https://www.cnblogs.com/YzaCsp/p/18654596