思路与算法

将所有词按字典序排序，用栈建立“最近的输入词前缀”父子森林，压缩掉不可被选择的非终止Trie节点。自底向上计算：若不选择当前词，孩子子树方案数相乘；若选择当前词，全部后代不能选，只有1种。因此dp=孩子乘积+1。森林各根再相乘，模9191。

正确性说明

字典序中同一前缀的所有后代连续出现，栈顶在弹出非前缀后就是最近的现有输入词祖先。不同孩子之间互不为前缀，可以独立选择；当前词与所有后代都冲突，所以选择当前词只允许空后代集。两类选择互斥且完整，底层乘积初值1同时计入空集，最终得到全部PFS子集。

复杂度

设总字节S≤50n。排序最坏O(n log n×50)，栈与前缀检查O(S)，自底向上O(n)，空间O(S+n)，初始化父亲/乘积数组O(n)。不创建250万个稠密26路节点，也不对模数做除法。

易错点

9191不要求是质数，本解只用加乘无需逆元。输入保证词互不相同，不能把重复词视作不同集合元素。独立小例枚举全部子集；最大规模等长不同词给出2^n，深前缀链森林给出各链“选至多一个”的乘积闭式。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<string> s(n);
    for (auto &w : s)
        cin >> w;
    sort(s.begin(), s.end());
    vector<int> parent(n, -1), stack;
    for (int i = 0; i < n; ++i) {
        while (!stack.empty() && s[i].compare(0, s[stack.back()].size(), s[stack.back()]) != 0)
            stack.pop_back();
        if (!stack.empty())
            parent[i] = stack.back();
        stack.push_back(i);
    }
    const int MOD = 9191;
    vector<int> product(n, 1);
    long long answer = 1;
    for (int i = n - 1; i >= 0; --i) {
        int value = (product[i] + 1) % MOD;
        if (parent[i] >= 0)
            product[parent[i]] = product[parent[i]] * value % MOD;
        else
            answer = answer * value % MOD;
    }
    cout << answer << '\n';
}