题目大意

给定 $n$ 个字符串，求有多少个子集满足：子集中恰好有 $k$ 对字符串互为变位词（即可以通过重新排列字母得到彼此）。

解题思路

关键观察

1. 变位词分组：互为变位词的字符串具有相同的字母组成
2. 配对计数：如果从同一组中选取 $j$ 个字符串，会产生 $\binom{j}{2}$ 对变位词
3. 独立计数：不同组之间的选择是独立的

算法步骤

1. 字符串哈希分组

// 使用随机权值计算字符串的"字母组成指纹"
for (int j = 0; j < 26; ++j)
    a[i] += cnt[j] * val[j];
++mp[a[i]];

2. 动态规划计数

定义 f[i] 表示产生恰好 $i$ 对变位词的方案数。

对于每组大小为 $t$ 的变位词组：

• 如果选择 $j$ 个字符串，会产生 $\binom{j}{2}$ 对变位词
• 从 $t$ 个字符串中选 $j$ 个的方案数为 $\binom{t}{j}$

状态转移：

for (int i = k; ~i; --i)
    if (f[i])
        for (int j = t; j; --j)
            if (i + j * (j - 1) / 2 <= k)
                add(f[i + j * (j - 1) / 2], 1ll * f[i] * C(t, j) % mod);

3. 组合数预处理

使用逆元预处理组合数，支持快速计算 $\binom{n}{m} \bmod 10^9+7$。

复杂度分析

• 时间复杂度：$O(n \cdot L + nk)$，其中 $L$ 是字符串最大长度
• 空间复杂度：$O(n + k)$

总结

本题通过变位词分组+动态规划计数的经典组合，将复杂的子集计数问题转化为分组背包问题。关键在于发现同一组内选择 $j$ 个字符串会产生 $\binom{j}{2}$ 对变位词，从而可以独立计算每组对总配对的贡献。