题解 CF1326F1 【Wise Men (Easy Version)】

皎月半洒花

2020-03-22 01:33:07

Solution

提供一种比较特别的easy的解法。 首先考虑,对于一个串 $s$ 而言,直接统计比较麻烦,麻烦在难以体现「不认识」这个限制上。所以考虑如何忽略这个限制。考虑忽略限制后,就变成了统计 $ans(s)$ 表示**至少**含有集合 $s$ 的排列数。 那么对于 $ans(s)$ 存在一个性质:如果 $s$ 和 $s'$ 中,连通分量状态相同,那么两个集合的 $ans$ 是等价的。此处连通分量指的是连续一段互相认识的人,状态相同指的是 $s$ 和 $s'$ 的这些段大小相同,排布可以不同。(比如 $0100111\Longleftrightarrow0011101\Longleftrightarrow1000111$) 。 证明很简单,因为对于生成 $01$ 的串而言,其方案数只在于有多少排列可以凑出这些 $1$ 的连续段而已。换言之就是由于是全排列,所以对称。 值得注意的是,对于一个长度为 $k$ 的 $1$ 连续段,其包含 $k+1$ 个互相认识的人,也就是该连通块大小为 $k+1$ 。 考虑如何求 $ans(s)$ 。注意到现在已经转化成了统计每一种对 $n$ 的拆分方式,有多少种排列数。那么一个比较自然的想法就是求下式 ![](https://cdn.luogu.com.cn/upload/image_hosting/h4x3figo.png) 其中 $t_i$ 表示枚举的第 $i$ 个点集,$s_i$ 表示组成 $s$ 这个 $01$ 串的第 $i$ 个连通块(链形态的点集) ,$f_{i,j}$ 表示从 $size(i)=j$ 的集合 $i$ 里面选出一个大小为 $j$ 的**链**的方案数。不难知道这些限制的意义:划分必须恰好划分掉 $n$ 个点,且点集之间不存在交集(否则需要合并)。 上式的意义在于,对于 $s$ 的一个划分,每个连通块都需要从某个点集中选出,而点集之间是互不相交的,所以 $size$ 必须恰好是链长。于是可以从这个角度入手来求排列数。同时需要注意,由于我们是硬生生划定了 $p$ 个集合,并不关心集合之间是否有连边,也就代表了其中有些单点(也就是 $s$ 中的 $0$ 位置)可能是与其他连通块是一体的,这也就符合了我们对 $ans(s)$ 的定义:**至少**含有集合 $s$ 的排列数。 注意到 $f$ 是比较容易求得的。考虑 $g_{i,j}$ 表示集合 $i$ 以 $j$ 结尾的链的方案数,那么就是 $n^2$ 转移,保证每次都用最后一个点转移就可以使得形态是一条链。$f$ 就是对 $g$ 的一个累加。这一部分复杂度 $O(n^22^n)$ 。 考虑求出 $f$ 之后如何计算这个式子。一个比较直接的想法是暴力枚举子集的子集来转移,由于 $\Pi$ 对 $\Sigma$ 有分配律,可知转移是不难的。复杂度 $P(n)3^n$,其中 $P(n)$ 是本质不同的划分数。可以过掉 $n=14$ 的 $\rm F1$ 。 代码就不放了,上述过程是比较浅显的。如果需要了解细节可以去我的Hard那个题解里看。