SimilarNames

作者 : 翁伊嘉

关键词 : 状压$dp$, 状态优化

题目概述

输入$n$个字符串，现在需要给它们从$0$到$n - 1$标号，满足$m$条形如 标号为$a_i$的字符串是标号为$b_i$的字符串的前缀 的限制。求标号方案数，模$10^9+7$输出。

$n$,字符串长度 $\le 50, m \le 8$

分析

考虑到前缀限制，容易想到先将给定字符串之间的前缀关系处理出来。添加一个空串为根，所有串之间的前缀关系构成了一个树的结构。

令有特殊限制的字符串总个数为$tot$,确定了这$tot$个字符串是哪些字符串后，剩下的字符串可以任意地给予编号，只要最后给答案乘上$(n - tot)!$即可。

注意到题中的$m \le 8$,也就是$tot$不超过$16$个，于是可以在树上进行状压$dp$。用$f_{x, S}$表示在以$i$为根的子树中选出$|S|$个字符串，对应到$S$所代表的标号集合的方案数。

考虑前缀限制，一个分配标号方案是合法的，当且仅当对于每一对限制$(a_i, b_i)$,$a_i$在前缀树上是$b_i$的祖先。由于我们的$dp$是以子树为状态的，考虑进一步转化这个限制——可以转化为，对于任意一棵子树，任意一个限制$(a_i, b_i)$中，或者没有一个编号在其中，或者只有$b_i$在其中，或者$a_i, b_i$均在其中。

根据这个，可以判断一个状态$S$是否合法。接着，只要在$dp$过程中，只考虑$S$合法的$f_{x, S}$，就能得到满足前缀限制的标号方案数了。

算法一

根据以上的分析，可以得到一个暴力的$dp$做法：

用${last}_{S}$保存，考虑以$x$为根的子树中的前$k - 1$个儿子，在它们之中分配$S$代表的标号集合的方案数。${now}_{S}$保存考虑前$k$个儿子时的值。

对于第$k$个儿子$son$，枚举前$k - 1$个儿子中用去的标号集合$A$,枚举这个儿子的子树中用去的标号集合$B$,用$f_{son,B} * {last}_{A}$更新${now}_{A + B}$

考虑完所有儿子之后，枚举根节点分配到的标号$id$，用${now}_S$更新$f_{x, S \cup \{id\}}$.或者不给根节点分配标号，用${now}_{S}$更新$f_{x, S}$

过程中，需要保证所有的状态均合法。状态的合法性可以提前处理出来。这样，总复杂度就是$O(n * 3^{tot})$。$3^{tot}$是合并儿子时子集枚举的复杂度。

算法二

由于状态的合法性可以预处理出来，$dp$时可以只枚举合法的状态。

可以证明合法的状态不超过$3^m$个。这是因为，对于一个限制$(a_i, b_i)$,它在状态$S$中只有三种合法的存在情况。这样，总的状态数就从$n * 2 ^ {tot}$降到了$n * 3 ^ {m}$

接下来，只要预处理出所有合法状态$S$的合法子集$A$,满足$A$与$S - A$均为合法状态，就可以用$O(n * 5 ^ m)$的时间完成$dp$.

预处理时只要$3^{tot}$直接枚举子集判断即可，接下来证明这样做了之后，合法子集的总个数是$5^m$级别的。

由于$A, S - A, S$均合法，对于每一对限制$(a_i, b_i)$,它们在$A$与$S - A$中的合法存在情况只有以下$5$种：

• $a_i, b_i$均在$A$中
• $a_i, b_i$均在$S - A$中
• $a_i, b_i$均不在$S$中
• 仅有$b_i$在$A$中
• 仅有$b_i$在$S - A$中

所以这样的组合$(S, A)$的总个数只有$5 ^ m$级别。$dp$时，直接枚举这样的合法组合进行转移。总的复杂度就是$O(3^{tot} + n * 5 ^ m)$了。

参考资料

SRM599 - TopCoder Wiki