题目分析

本题要求计算恰好与给定的 $N$ 个字符串中 $K$ 个匹配的字符串 $T$ 的数量，其中匹配的条件是：对于字符串 $S_x$，$T$ 的长度与 $S_x$ 相同，且每个位置上 $T$ 的字符要么等于 $S_x$ 的字符，要么 $S_x$ 的字符是 ?。由于直接计算“恰好 $K$ 个”较为困难，我们可以借助容斥原理结合状态压缩枚举来解决。

算法标签

容斥原理、

状态压缩枚举、

组合数学

算法思路

1. 状态压缩枚举子集

由于 $N \leq 15$，我们可以用二进制数枚举所有可能的字符串子集（共 $2^N$ 种）。对于每个子集，我们需要判断该子集中的所有字符串是否“可兼容”（即对于每个位置，子集中的字符串在该位置的非 ? 字符必须相同）。若可兼容，则计算能匹配该子集所有字符串的 $T$ 的数量（未被确定的位置可自由选择26个小写字母）。

2. 容斥原理计算恰好匹配数

我们先统计“至少匹配 $t$ 个字符串”的数量 sum[t]，再通过容斥公式将其转换为“恰好匹配 $t$ 个字符串”的数量。容斥的核心思想是：

$$\text{恰好} \ k = \text{至少} \ k - \binom{k+1}{k} \times \text{至少} \ k+1 + \binom{k+2}{k} \times \text{至少} \ k+2 - \dots $$

通过预处理组合数，我们可以从后往前递推得到最终的“恰好 $K$ 个”的结果。

具体步骤

1. 预处理组合数：使用递推法预处理组合数 $C(n, k)$，用于后续容斥计算。
2. 枚举所有子集：对于每个子集，检查其内部字符串是否兼容，若兼容则计算该子集对“至少 $t$ 个”（$t$ 为子集大小）的贡献。
3. 容斥计算恰好匹配数：利用预处理的组合数，从后往前递推调整“至少 $t$ 个”的数量，得到“恰好 $K$ 个”的结果。

复杂度分析

• 枚举子集的时间复杂度：$O(2^N \times N \times \text{len})$，其中 $N \leq 15$，$\text{len} \leq 50$，因此 $2^{15} \times 15 \times 50 = 2,457,600$，可轻松处理。
• 容斥计算的时间复杂度：$O(N^2)$，$N \leq 15$，耗时可忽略。

综上，该算法的时间复杂度为 $O(T \times (2^N \times N \times \text{len} + N^2))$，能够高效处理题目给定的数据范围。