题解 CF1326F2 【Wise Men (Hard Version)】

皎月半洒花

2020-03-22 01:34:48

Solution

个人感觉写的比其他题解要详细? 不过这题本质上跟FWT的and卷积没啥关系…不知道某些老哥是怎么理解的…就只是单纯的长得像而已… ____________ 首先考虑,对于一个串 $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$ 。 对于 $\rm F2$ ,考虑这么一个问题:如何保证一组相加起来 $size$ 等于全集的子集互不相交?很显然是如果他们的**并**就是全集,那么彼此之间一定不会有交。于是可以知道用 FMT 来优化这个过程。具体的,根据分配律,可以对每个 $s_i$ 分开计算其贡献,进行 $p$ 次 FMT 之后,答案就是第 $2^n-1$ 项系数。 那么就做完了。最后只需对于每个 $01$ 串,求出他的划分即可。注意到一开始 $ans$ 的定义,需要我们做一次子集差变换。大概类似于FMT处理and的逆过程。最终复杂度 $O(2^n(P(n)+n+n^2))$ 。 ```cpp #include <bits/stdc++.h> using namespace std ; #define p_p pop_back #define p_b push_back #define vint vector<int> typedef long long ll ; const int N = 20 ; const int M = 1200000 ; int n ; int m ; int tot ; ll I[M] ; ll t[M] ; ll ans[M] ; ll f[M][N] ; ll g[N][M] ; ll res[N * N] ; int know[N][N] ; map<vint, int> Id ; vint part[N * N], now ; void fmt_or(ll *f, int g){ int i, j ; for (i = 0 ; i < n ; ++ i) for (j = 0 ; j <= m ; ++ j) if (j >> i & 1) f[j] = f[j] + (ll)g * f[j ^ (1 << i)] ; } void dfs_part(int st, int big){ if (st == n + 1) return void(part[Id[now] = ++ tot] = now) ; if (n - st + 1 >= big){ for (int i = big ; i <= n - st + 1 ; ++ i) now.p_b(i), dfs_part(st + i, i), now.p_p() ; } } void dp1(){ for (int i = 0 ; i < n ; ++ i) f[1 << i][i + 1] = 1 ; for (int i = 1 ; i <= m ; ++ i){ int len = 0 ; for (int j = 1 ; j <= n ; ++ j){ if (1 << (j - 1) & ~i) continue ; for (int k = 1 ; k <= n ; ++ k){ if (!know[j][k]) continue ; if (1 << (k - 1) & i) continue ; f[i | (1 << (k - 1))][k] += f[i][j] ; } ++ len ; } for (int j = 1 ; j <= n ; ++ j) if (1 << (j - 1) & i) g[len][i] += f[i][j] ; } } void dp2(){ for (int i = 1 ; i <= tot ; ++ i){ memcpy(t, I, sizeof(I)) ; int o = (int)part[i].size() ; for (int j = 0 ; j < o ; ++ j) for (int k = 0 ; k <= m ; ++ k) t[k] *= g[part[i][j]][k] ; fmt_or(t, -1) ; res[i] = t[m] ; } //for (int i = 1 ; i <= tot ; ++ i) cout << res[i] << " " ; puts("") ; } void revalue(){ for (int i = 0 ; i <= m ; ++ i){ now.clear() ; for (int l = 0, r ; l < n ; l = r + 1){ r = l ; while ((1 << r) & i && r < n) ++ r ; now.p_b(r - l + 1) ; } sort(now.begin(), now.end()) ; ans[i] = res[Id[now]] ; } } int main(){ cin >> n ; m = (1 << n) - 1 ; I[0] = 1 ; fmt_or(I, 1) ; for (int i = 1 ; i <= n ; ++ i) for (int j = 1 ; j <= n ; ++ j) scanf("%1d", &know[i][j]) ; dp1() ; for (int i = 1 ; i <= n ; ++ i) fmt_or(g[i], 1) ; /* for (int i = 1 ; i <= n ; ++ i) for (int j = 1 ; j <= m ; ++ j) cout << g[i][j] << " \n"[j == m] ; */ dfs_part(1, 1) ; dp2() ; revalue() ; //for (int j = 1 ; j <= m ; ++ j) // cout << I[j] << " " ; puts("") ; ((m += 1) >>= 1) -= 1 ; for (int i = 0 ; i < n ; ++ i) for (int j = m ; j >= 0 ; -- j) if (~j >> i & 1){ ans[j] = ans[j] - ans[j | (1 << i)] ; } for (int i = 0 ; i <= m ; ++ i) cout << ans[i] << " \n"[i == m] ; return 0 ; } ```