特殊性质

模拟即可，时间复杂度 $O(\sum |s_i|)$，期望得分 $10$。

$n\le 12$

考虑状态压缩 dp，设 $f_{i,S}$ 表示将集合 $S$ 中的所有串插入到一个深度为 $i$ 的节点的方案数。

使用枚举子集的方式分裂 $S$ 到 $i+1$ 去转移，时间复杂度 $O(3^n|s_i|)$。貌似可以用高维前缀和优化到 $O(2^n|s_i|n)$。期望得分 $50$。

$n\le 20$

正解和特殊性质关系不大。个人觉得正解要比特殊性质好写。

不难发现，若确定了每个字符串 $s_i$，则字典树的节点个数为：

$$\sum_{S}(-1)^{|S|-1}\text{LCP}(S)$$

其中 $\text{LCP}(S)$ 表示集合 $S$ 中所有字符串的最长公共前缀。

好的，若 $s_i$ 未确定，如何计算 $\text{LCP}(S)$其实非常简单？枚举最长公共前缀的长度 $i$，只需要保障前 $i$ 位相同，第 $i+1$ 位不相同即可，时间复杂度为 $O(2^n|s_i|)$，期望得分 $100$。