0%

「ZJOI2016」小星星

「ZJOI2016」小星星

给一棵树 $ T $ 和一个图 $ G $ ,求将 $ T $ 上的点重标号后为 $ G $ 的子图的方案数。

$ n\le 17 $ .

考虑状压dp。令 $ f(u,x,S) $ 表示以 $ u $ 为根的子树,标号的点集为 $ S $ 且 $ u $ 的标号是 $ x $ .( $ x $ 这一维不能少,因为转移时我们要判断边是否存在于 $ G $ 中)

转移:( $ v_i $ 表示第 $ i $ 个儿子)

爆算是 $ \mathcal O(n^33^n) $ 或 $ \mathcal O(n^23^n) $ 的。发现 $ T_i $ 的关系是不相交集合,可以用子集卷积做到 $ \mathcal O(2^n n^4) $ .这样也是过不去的。

法一:

但事实上我们不需要子集卷积。。对于有交集的情况,我们得到的集合大小一定是小于 $ u $ 的子树大小的,那么最后的答案 $ \sum_{x}f(1,x,\{1,2,…,n\}) $ 一定不包含这些情况。所以FWT之后直接卷就好了。复杂度 $ \mathcal O(2^nn^3) $ .

法二:

考虑去掉 $ S $ 这一维的影响:求出的方案可能包含了图上一个点被多个树上的点映射的情况。那么我们可以用映射到至多 $ n $ 个点的方案减去映射到之多 $ n-1 $ 个点的方案再加上映射到至多 $ n-2 $ 个点的方案….即:

其中 $ f(S,1,x) $ 表示只允许映射 $ S $ 中的点,且 $ 1 $ 映射了 $ x $ 的方案数。枚举 $ S $ ,求解 $ f(S,1,x) $ 的复杂度是 $ \mathcal O(n^3) $ 的所以总复杂度是 $ \mathcal O(2^nn^3) $ 。

个人认为法一不用脑子,是最吼的