把集合建成字典树,树上求 f[v]=儿子答案之积+[v 是词尾],排序后用相邻最长公共前缀代替建树,答案即 f[根] 对 9191 取模。
OJ: roj
题目 ID: 1700
难度:普及+/提高-
标签:字符串字典树树形 DPpython
创建: 2026-10-07 15:57
更新: 2026-10-07 15:57
形式化题目
给定
空集没有两两前缀的约束,恒合法,因此答案至少为
正解
思路
前缀关系天然长在字典树上。 前缀是一种传递关系,
于是合法子集
任意两个被选中的标记点之间,不能存在祖先关系。
这正是树上的「反链」(antichain),只不过这里的树是 trie,且允许选空集。
树上做 DP。 设
- 选
本身(前提是 被标记为词尾):一旦选了 ,它的所有后代都不能再选, 方案数是 ; - 不选
:各棵子树完全独立,方案数是 。
两件事互斥且穷尽,所以
叶子满足
为什么"不选
用样例手算验证一下。三个串 hell — hello 的链挂在 h 下、hi 另起一枝:
| 节点(前缀) | 是否词尾 | ||
|---|---|---|---|
hell |
是 | ||
hello |
是 | ||
hi |
是 | ||
| 根 | 否 |
答案 hell,hellohi,hello,hell
代码
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++ 版(同一算法):
/**
* 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 叉字典树数组:总字符数可达
int,远超题目内存限制。
关键是注意到:把串按字典序排序后,同一个节点的所有后代在数组里正好是一段连续的区间,
而第
- 处理第
个串时,先用相邻 LCP 求出它父亲的深度 lcp; - 把栈里所有深度
的节点弹出,每弹一个就把它的 乘进父亲的累乘值; - 再把当前串作为一个深度为
的词尾节点压栈。
栈里留下的都是"还没算完的祖先",深度严格递增,一个节点的父亲就是栈中它下面那个。
中间那些「既不是词尾、又只有一个儿子」的节点(如 hell 与 hello 之间的过渡前缀)
被整段跳过——它们的
以 a、ab 为例(答案 a 先入栈(深度 1,词尾);
处理 ab 时 LCP 为 ab(a,再弹 a(
复杂度
- 时间:排序
次字符比较;LCP 的总比较次数不超过各串长度之和的 常数倍(相邻 LCP 的单调性保证均摊 );栈的入出各一次 。 于是 ,其中 。 真实数据最大点 、总长 ,C++ 实测远低于限时 ms。 - 空间:
word[]存全部串,手工栈与 Python 的栈各 (栈最大深度不超过最长串的长度 )。没有 26 叉儿子数组,内存是 。 - 与标准 trie 的关系:常见写法是直接开 26 叉 trie 再 DFS 求
,算法完全一样, 但空间多一个 倍常数; main.cpp与main.py用「排序 + 相邻 LCP」把这一项省掉, 代码也更短。注意这里不需要考虑是否为质数:DP 只用到乘法和加法。
总结
- 前缀关系 = 祖先关系:看到「若干串两两不为前缀」,第一反应应该是把串插进 trie, 题目就从字符串问题变成树上的组合计数问题。
- 树形 DP 的转移由"选不选自己"唯一决定:选了自己后代全禁(贡献
), 不选则各子树独立(贡献连乘)。这条 是本题的全部内容。 - 子树独立 ⇒ 乘法原理:一旦把选题拆成"每棵子树各贡献一个子集", 乘法就是唯一正确的合并方式;写成加法是本题最典型的错误。
- 不必真的建树:排序 + 相邻 LCP 能还原 trie 的父子关系, 对"只需要知道父子关系、不需要按字符转移"的 trie 题,这是省内存省代码的通用技巧。
- 空集恒合法,被
的"全不选"分支自动计入,无需单独处理。