【题解】Codeforces [Global Round 7F] Wise Men

有 $n$ 个人。给出 $n$ 个人的「认识情况」(双向且保证合法)。

定义 bool 值函数 $K(i,j)$ 表示两个人是否认识。考虑一个 $n$ 个人编号的排列 $p$ ,定义其生成的 $01$ 串 $\{s_{n-1}\}$ 为 $\forall i\in[1,n-1]\cap\mathbb{Z_+},s_i=K(p_{i},p_{i+1})$。

统计对于 $2^{n-1}$ 种不同的 $01$ 串,有多少种排列可以生成它。

F1: $2\leq n\leq 14$ 。

F2 : $2\leq n\leq 18$ 。

神仙计数题,再一次深深地明白了自己的弱小。

首先考虑,对于一个串 $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$ 的拆分方式,有多少种排列数。那么一个比较自然的想法就是求下式

其中 $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))$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#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 ;
}

撒花撒花!!