wordgame 题解（不了一点）

题目：文字游戏（wordgame）

题目描述

在文字游戏中，共有 $n$ 种卡牌，每种卡牌上有一个字符串。每轮可以选择不超过 $m$ 张卡牌。权值的计算方式为所有选中的字符串长度之和减去它们的最长公共前缀（LCP）长度乘以卡牌数量。求所有合法出牌方式的权值之和模 $10^9+7$。

输入格式

• 第一行：$n$ 和 $m$。
• 接下来 $n$ 行：每行一个字符串。
• 最后一行：$n$ 个整数，表示每种卡牌的数量 $v_i$。

输出格式

输出权值之和模 $10^9+7$。

---

题目分析

1. 权值计算：权值 $V_s$ 分为两部分：

   • 总长度之和 $A$：所有选中字符串的长度之和。
   • LCP 总贡献 $B$：所有组合的最长公共前缀长度的总和。
     最终答案为 $A - B$。

2. 关键难点：

   • 高效计算所有可能的组合，避免枚举。
   • 利用数据结构（Trie）高效统计 LCP 的贡献。

---

解题思路

总长度之和 $A$ 的计算

• 生成函数：每个字符串的生成函数为 $\sum_{k=0}^m C(v_i, k)x^k$，表示选 $k$ 张该卡的方式数。
• 多项式乘法：所有字符串的生成函数相乘，得到总组合数。
• 贡献计算：对于每个字符串，计算其在所有组合中的出现次数总和，乘以长度。

LCP 贡献 $B$ 的计算

• Trie 树：构建 Trie 树，每个节点代表一个前缀。
• 动态规划：后序遍历 Trie，计算每个节点的组合数：
  • 节点的组合数 = 所有子节点组合数的乘积 × 当前节点的组合数。
  • 贡献为：节点深度 × (当前组合数 - 子节点组合数之和)。

---

实现细节

1. 生成函数乘法与除法：

   • 预处理每个字符串的生成函数。
   • 计算总生成函数后，通过递推求排除某个字符串后的生成函数，避免重复计算。

2. Trie 树优化：

   • 使用数组存储子节点，加速访问。
   • 后序遍历合并子节点的动态规划数组。

3. 组合数计算：

   • 使用预计算的阶乘逆元加速组合数计算。

---

易错点

1. 模运算处理：减法后需确保结果非负。
2. 生成函数除法：递推计算时需正确处理多项式逆元。
3. Trie 节点合并：子节点的组合数需正确卷积到父节点。

---

完整代码

#include <iostream>
#include <vector>
#include <unordered_map>
#include <memory>
#include <cstring>
#include <algorithm>

using namespace std;

const int MOD = 1e9 + 7;
const int MAXM = 5;

int fact_inv[MAXM + 1] = {1, 1, 500000004, 166666668, 41666667, 808333339};

struct TrieNode {
    TrieNode* children[26];
    int depth;
    vector<int> a;
    vector<int> dp;

    TrieNode(int d, int m) : depth(d), a(m + 1, 0), dp(m + 1, 0) {
        memset(children, 0, sizeof(children));
    }
};

int comb(int v, int k) {
    if (k == 0) return 1;
    long long res = 1;
    for (int i = 0; i < k; ++i) {
        res = res * (v - i) % MOD;
    }
    return res * fact_inv[k] % MOD;
}

void insertTrie(TrieNode* root, const string& s, const vector<int>& poly) {
    TrieNode* node = root;
    for (char c : s) {
        int idx = c - 'a';
        if (!node->children[idx]) {
            node->children[idx] = new TrieNode(node->depth + 1, root->dp.size() - 1);
        }
        node = node->children[idx];
    }
    for (int k = 0; k < poly.size(); ++k) {
        node->a[k] = (node->a[k] + poly[k]) % MOD;
    }
}

void computeDp(TrieNode* node, int m, int& B) {
    for (int i = 0; i < 26; ++i) {
        if (node->children[i]) {
            computeDp(node->children[i], m, B);
        }
    }

    fill(node->dp.begin(), node->dp.end(), 0);
    node->dp[0] = 1;

    for (int i = 0; i < 26; ++i) {
        if (!node->children[i]) continue;
        TrieNode* child = node->children[i];
        vector<int> tmp(m + 1, 0);
        for (int a = 0; a <= m; ++a) {
            if (node->dp[a] == 0) continue;
            for (int b = 0; b <= m - a; ++b) {
                tmp[a + b] = (tmp[a + b] + 1LL * node->dp[a] * child->dp[b]) % MOD;
            }
        }
        node->dp = tmp;
    }

    vector<int> new_dp = node->dp;
    for (int k = m; k >= 0; --k) {
        for (int a = 1; a <= min(k, (int)node->a.size() - 1); ++a) {
            new_dp[k] = (new_dp[k] + 1LL * new_dp[k - a] * node->a[a]) % MOD;
        }
    }
    node->dp.swap(new_dp);

    int sumk = 0;
    for (int k = 1; k <= m; ++k) {
        sumk = (sumk + 1LL * k * node->dp[k]) % MOD;
    }

    int sum_child = 0;
    for (int i = 0; i < 26; ++i) {
        if (!node->children[i]) continue;
        TrieNode* child = node->children[i];
        int sk = 0;
        for (int k = 1; k <= m; ++k) {
            sk = (sk + 1LL * k * child->dp[k]) % MOD;
        }
        sum_child = (sum_child + sk) % MOD;
    }

    int contrib = (1LL * node->depth * ((sumk - sum_child + MOD) % MOD)) % MOD;
    B = (B + contrib) % MOD;
}

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

    int n, m;
    cin >> n >> m;

    vector<string> s(n);
    for (int i = 0; i < n; ++i) {
        cin >> s[i];
    }

    vector<int> v(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }

    unordered_map<string, int> sum_v_map;
    for (int i = 0; i < n; ++i) {
        if (v[i] > 0) {
            sum_v_map[s[i]] = (sum_v_map[s[i]] + v[i]) % MOD;
        }
    }

    vector<pair<string, int>> unique_strings;
    for (const auto& p : sum_v_map) {
        unique_strings.emplace_back(p.first, p.second);
    }

    if (unique_strings.empty()) {
        cout << "0\n";
        return 0;
    }

    vector<int> coeff_total(m + 1, 0);
    coeff_total[0] = 1;
    vector<vector<int>> polys;
    for (const auto& p : unique_strings) {
        int current_v = p.second;
        vector<int> poly(m + 1, 0);
        for (int k = 0; k <= m; ++k) {
            poly[k] = comb(current_v, k);
        }
        polys.push_back(poly);

        vector<int> new_coeff(m + 1, 0);
        for (int a = 0; a <= m; ++a) {
            if (coeff_total[a] == 0) continue;
            for (int b = 0; b <= m - a; ++b) {
                new_coeff[a + b] = (new_coeff[a + b] + 1LL * coeff_total[a] * poly[b]) % MOD;
            }
        }
        coeff_total = new_coeff;
    }

    int A = 0;
    for (int idx = 0; idx < unique_strings.size(); ++idx) {
        const auto& p = unique_strings[idx];
        const string& str = p.first;
        int len_s = str.size();
        const vector<int>& poly = polys[idx];

        vector<int> coeff_rest(m + 1, 0);
        coeff_rest[0] = 1;
        for (int k = 1; k <= m; ++k) {
            long long val = coeff_total[k];
            for (int t = 1; t <= min(k, m); ++t) {
                val -= 1LL * coeff_rest[k - t] * poly[t] % MOD;
                if (val < 0) val += MOD;
            }
            coeff_rest[k] = val % MOD;
        }

        vector<int> prefix(m + 2, 0);
        for (int k = 0; k <= m; ++k) {
            prefix[k + 1] = (prefix[k] + coeff_rest[k]) % MOD;
        }

        long long sum = 0;
        for (int k = 1; k <= m; ++k) {
            int max_other = m - k;
            if (max_other < 0) continue;
            sum = (sum + 1LL * poly[k] * k % MOD * prefix[max_other + 1] % MOD) % MOD;
        }
        A = (A + 1LL * len_s * sum % MOD) % MOD;
    }

    TrieNode root(0, m);
    for (int i = 0; i < unique_strings.size(); ++i) {
        insertTrie(&root, unique_strings[i].first, polys[i]);
    }

    int B = 0;
    computeDp(&root, m, B);

    int ans = (A - B + MOD) % MOD;
    cout << ans << "\n";

    return 0;
}

---

总结

通过生成函数和 Trie 树的结合，高效处理了大规模组合计数与公共前缀统计问题，确保时间复杂度在 $O(\text{sumlen} \cdot m^2)$，适用于题目给定的数据范围。