PFS集合

GitHub跳转原题关系图返回列表

把集合建成字典树,树上求 f[v]=儿子答案之积+[v 是词尾],排序后用相邻最长公共前缀代替建树,答案即 f[根] 对 9191 取模。

OJ: roj

题目 ID: 1700

难度:普及+/提高-

标签:字符串字典树树形 DPpython

创建: 2026-10-07 15:57

更新: 2026-10-07 15:57

形式化题目

给定 nn 个互不相同的非空字符串 s1,s2,…,sns_1, s_2, \dots, s_n(均为小写字母串),求

#{ T⊆{s1,…,sn}  ∣  ∀ x≠y∈T,  x 不是 y 的前缀 } mod 9191. \#\Bigl\{\, T \subseteq \{s_1, \dots, s_n\} \;\Bigm|\; \forall\, x \neq y \in T,\; x \text{ 不是 } y \text{ 的前缀} \,\Bigr\} \bmod 9191 .

空集没有两两前缀的约束,恒合法,因此答案至少为 11。约束是 n⩽50000n \leqslant 50000、 ∣si∣⩽50|s_i| \leqslant 50,串的总长不超过 2.5×1062.5 \times 10^6。

正解

思路

前缀关系天然长在字典树上。 前缀是一种传递关系,xx 是 zz 的前缀且 yy 是 xx 的前缀 就说明 yy 也是 zz 的前缀;把 sis_i 插进一棵 26 叉字典树、在词尾节点上打标记后, 「xx 是 yy 的前缀」就等价于「xx 对应的标记点是 yy 对应标记点的祖先」。

于是合法子集 TT 的判定被翻译成一棵有根树上的组合条件:

任意两个被选中的标记点之间,不能存在祖先关系。

这正是树上的「反链」(antichain),只不过这里的树是 trie,且允许选空集。

树上做 DP。 设 f[v]f[v] 表示「以 vv 为根的那棵子树里,只在标记点中挑、且挑出的点两两 不成祖先」的方案数。对 vv 分类:

  • 选 vv 本身(前提是 vv 被标记为词尾):一旦选了 vv,它的所有后代都不能再选, 方案数是 11;
  • 不选 vv:各棵子树完全独立,方案数是 ∏儿子 cf[c]\prod_{\text{儿子 } c} f[c]。

两件事互斥且穷尽,所以

  f[v]=[ v 是词尾 ]+∏c 是 v 的儿子f[c]   \boxed{\;f[v] = [\,v \text{ 是词尾}\,] + \prod_{c \text{ 是 } v \text{ 的儿子}} f[c] \;}

叶子满足 f=[ 叶子是词尾 ]f = [\,\text{叶子是词尾}\,];根(空串对应的节点)不是任何输入的串, 所以 f[root]=∏cf[c]f[\text{root}] = \prod_{c} f[c] 恰好就是答案——空集这一种方案被 ff 的「全不选」 分支自动计入,不需要额外加 11。

为什么"不选 vv"是连乘而不是求和? 因为子树之间没有公共字符串, 一个方案由「每棵子树里各选一个(可能为空的)合法子集」唯一确定, 乘法原理把它们拼起来。这一点也是本题最容易写错的地方: 写成 ∑\sum 会把"只在某一棵子树里选"误当成唯一选择,漏掉跨子树的搭配。

用样例手算验证一下。三个串 {hell,hello,hi}\{\text{hell}, \text{hello}, \text{hi}\} 的 trie 是 hell — hello 的链挂在 h 下、hi 另起一枝:

节点(前缀) 是否词尾 ∏f[儿子]\prod f[\text{儿子}] f[v]f[v]
hell 是 f[hello]=2f[\text{hello}] = 2 2+1=32 + 1 = 3
hello 是 11(无儿子) 1+1=21 + 1 = 2
hi 是 11(无儿子) 1+1=21 + 1 = 2
根 否 3×2=63 \times 2 = 6 66

答案 66,与题面"只有 {\{hell,hello}\} 和 {\{hi,hello,hell}\} 两种不合法" (23=82^3 = 8 减 22)吻合。

代码

Python 版:

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 15:55
# update_at: 2026-10-07 15:55

import sys

MOD = 9191  # 题目要求的取模值

# 类型别名:trie 上的一个节点 = (深度, 已并入的儿子答案累乘值, 自己是否为单词结尾)
type Frame = tuple[int, int, int]
type Stack = list[Frame]  # 手工栈:栈底是根,越靠近栈顶深度越大,父亲就是栈中下一个元素


def fold_top(stack: Stack) -> None:
    """弹出栈顶节点,把它的答案乘进父亲的累乘值。

    f[v] = 儿子答案之积 + (v 是单词结尾 ? 1 : 0):
    乘积那部分对应「不选 v」,加上的 1 对应「只选 v,子树里一个都不选」。
    """
    depth, prod, is_end = stack.pop()
    pdepth, pprod, pis_end = stack[-1]
    stack[-1] = (pdepth, pprod * (prod + is_end) % MOD, pis_end)


def count_pfs(words: list[str]) -> int:
    """排序后用相邻最长公共前缀还原 trie 结构,逐节点统计合法子集数(含空集)。"""
    words.sort()
    stack: Stack = [(0, 1, 0)]  # 根:深度 0、累乘初值 1、不是任何单词的结尾
    prev = ""
    for word in words:
        lcp = 0  # 与上一个串的最长公共前缀长度 = 本串所在节点的父亲深度
        while lcp < len(word) and lcp < len(prev) and word[lcp] == prev[lcp]:
            lcp += 1
        while stack[-1][0] > lcp:  # 收掉所有比父亲更深的节点
            fold_top(stack)
        stack.append((len(word), 1, 1))  # 当前字符串自己是一个结尾节点
        prev = word
    while len(stack) > 1:  # 最后把整条路径收拢回根
        fold_top(stack)
    return stack[0][1] % MOD


def solve() -> None:
    data = sys.stdin.buffer.read().split()
    n = int(data[0])  # 题目保证 n >= 1
    words = [token.decode() for token in data[1:1 + n]]  # 需要整体排序,故一次性物化成列表
    print(count_pfs(words))


if __name__ == "__main__":
    solve()

C++ 版(同一算法):

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-07 15:55
 * update_at: 2026-10-07 15:55
 */
// main.cpp:PFS 集合,字典树上数「两两不成前缀」的子集个数。
// 与 main.py 同一算法:把字符串按字典序排序,第 i 个串在 trie 中的父节点深度就是
// 它与前一个串的最长公共前缀长度,于是不必真的开出 26 叉字典树,
// 只用一个手工栈按深度收拢节点即可完成同样的树形 DP。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MOD = 9191;    // 题目要求的取模值
const int MAXN = 50005;  // 字符串个数上限

// trie 上的一个节点。只保留「单词结尾」与「分叉点」:
// 不是结尾且只有一个儿子的节点,其答案等于儿子的答案,可以整段跳过。
struct Frame {
    ll depth;   // 该节点对应的前缀长度
    ll prod;    // 已并入的儿子答案累乘值
    ll is_end;  // 该前缀本身是不是一个单词(0/1)
};

string word[MAXN];  // 按字典序排序后的所有字符串
Frame stk[MAXN];    // 手工栈:stk[0] 是根(深度 0,不是任何单词的结尾),stk[top_cnt] 是当前最深节点
ll top_cnt;         // 栈顶下标

// 弹出栈顶节点,把它自己的答案乘进父亲的累乘值。
// f[v] = (所有儿子 f 的乘积) + (v 是单词结尾 ? 1 : 0):
// 乘积那部分对应「不选 v,在每棵子树里各选一个合法子集」,
// 加上的 1 对应「选 v,则子树里一个都不能再选」。
void fold_top() {
    ll f_val = (stk[top_cnt].prod + stk[top_cnt].is_end) % MOD;
    top_cnt--;
    stk[top_cnt].prod = stk[top_cnt].prod * f_val % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n;
    cin >> n;
    for (ll i = 0; i < n; i++) cin >> word[i];
    sort(word, word + n);  // 同一前缀的串排在一起,子树变成连续区间

    stk[0].depth = 0;   // 根节点
    stk[0].prod = 1;    // 累乘初值
    stk[0].is_end = 0;  // 空串不是输入里的元素
    top_cnt = 0;

    ll prev_len = 0;  // 上一个字符串的长度
    for (ll i = 0; i < n; i++) {
        ll len = word[i].size();
        ll lcp = 0;
        if (i > 0) {
            // 与上一个串的最长公共前缀长度,就是本串所在节点的父亲深度
            ll lim = min(len, prev_len);
            while (lcp < lim && word[i][lcp] == word[i - 1][lcp]) lcp++;
        }
        while (stk[top_cnt].depth > lcp) fold_top();  // 收掉比父亲更深的节点
        top_cnt++;
        stk[top_cnt].depth = len;
        stk[top_cnt].prod = 1;
        stk[top_cnt].is_end = 1;  // 当前字符串本身是一个结尾节点
        prev_len = len;
    }
    while (top_cnt > 0) fold_top();  // 把整条路径收拢回根

    cout << stk[0].prod % MOD << '\n';  // 根的累乘值就是答案(空集已被算作一种)
    return 0;
}

不建树也能建树。 两个正式解都没有真的开出 26 叉字典树数组:总字符数可达 2.5×1062.5 \times 10^6,如果每个节点都存 26 个儿子编号,光空间就是 2.6×1082.6 \times 10^8 个 int,远超题目内存限制。

关键是注意到:把串按字典序排序后,同一个节点的所有后代在数组里正好是一段连续的区间, 而第 ii 个串的「父亲深度」就是它与前一个串的最长公共前缀长度(LCP)。 于是只要一个手工栈按深度收拢节点,就能在 O(1)O(1) 均摊时间里模拟出树的进出栈次序:

  • 处理第 ii 个串时,先用相邻 LCP 求出它父亲的深度 lcp;
  • 把栈里所有深度 >lcp> \text{lcp} 的节点弹出,每弹一个就把它的 ff 乘进父亲的累乘值;
  • 再把当前串作为一个深度为 ∣si∣|s_i| 的词尾节点压栈。

栈里留下的都是"还没算完的祖先",深度严格递增,一个节点的父亲就是栈中它下面那个。 中间那些「既不是词尾、又只有一个儿子」的节点(如 hell 与 hello 之间的过渡前缀) 被整段跳过——它们的 ff 恒等于唯一儿子的 ff,跳过不影响答案。

以 a、ab 为例(答案 33):排序后 a 先入栈(深度 1,词尾); 处理 ab 时 LCP 为 11,栈顶深度 11 不弹出,直接压入深度 22 的词尾节点; 收尾时先弹 ab(f=1+1=2f = 1 + 1 = 2)乘进 a,再弹 a(f=2+1=3f = 2 + 1 = 3)乘进根, 输出 33。与 trie 上的 ff 完全一致。

复杂度

  • 时间:排序 O(nlog⁡n⋅L)O(n \log n \cdot L) 次字符比较;LCP 的总比较次数不超过各串长度之和的 常数倍(相邻 LCP 的单调性保证均摊 O(总长)O(\text{总长}));栈的入出各一次 O(n)O(n)。 于是 O(nlog⁡n⋅L+总长)O(n \log n \cdot L + \text{总长}),其中 L⩽50L \leqslant 50。 真实数据最大点 n=50000n = 50000、总长 2.5×1062.5 \times 10^6,C++ 实测远低于限时 10001000 ms。
  • 空间:word[] 存全部串 O(总长)O(\text{总长}),手工栈与 Python 的栈各 O(n)O(n) (栈最大深度不超过最长串的长度 5050)。没有 26 叉儿子数组,内存是 O(总长+n)O(\text{总长} + n)。
  • 与标准 trie 的关系:常见写法是直接开 26 叉 trie 再 DFS 求 ff,算法完全一样, 但空间多一个 2626 倍常数;main.cpp 与 main.py 用「排序 + 相邻 LCP」把这一项省掉, 代码也更短。注意这里不需要考虑 91919191 是否为质数:DP 只用到乘法和加法。

总结

  • 前缀关系 = 祖先关系:看到「若干串两两不为前缀」,第一反应应该是把串插进 trie, 题目就从字符串问题变成树上的组合计数问题。
  • 树形 DP 的转移由"选不选自己"唯一决定:选了自己后代全禁(贡献 11), 不选则各子树独立(贡献连乘)。这条 f[v]=[词尾]+∏f[c]f[v] = [\text{词尾}] + \prod f[c] 是本题的全部内容。
  • 子树独立 ⇒ 乘法原理:一旦把选题拆成"每棵子树各贡献一个子集", 乘法就是唯一正确的合并方式;写成加法是本题最典型的错误。
  • 不必真的建树:排序 + 相邻 LCP 能还原 trie 的父子关系, 对"只需要知道父子关系、不需要按字符转移"的 trie 题,这是省内存省代码的通用技巧。
  • 空集恒合法,被 ff 的"全不选"分支自动计入,无需单独处理。