题解

问题转化

设我们选择的结尾字母集合为 $X$（$X \subseteq \{0,1,\dots,c-1\}$，每个数字对应一个字母）。我们需要将字符串分割成若干单词，每个单词长度 $\le k$ 且最后一个字母属于 $X$。

关键观察：这样的分割存在当且仅当以下两个条件同时成立：

1. 字符串的最后一个字符 $s[n-1] \in X$。
2. 所有长度为 $k$ 的连续子串（窗口）都至少包含一个 $X$ 中的字母。

必要性：若存在一个长度为 $k$ 的窗口不含 $X$ 中的字母，则该窗口无法被任何一个长度 $\le k$ 的单词覆盖（因为单词的结尾必须在 $X$ 中，而该窗口内没有 $X$ 字母，且窗口长度为 $k$，任何跨越该窗口的单词长度都会超过 $k$）。最后一个字符必须属于 $X$ 是显然的。

充分性：当上述两个条件满足时，可以采用贪心策略：从位置 $0$ 开始，每次选择当前能到达的最远位置 $j$（满足 $j$ 是 $X$ 中的字母且 $j - \text{当前位置} + 1 \le k$），然后移动到 $j+1$。由于每个长度为 $k$ 的窗口都有 $X$ 字母，这个过程总能继续，最终覆盖整个字符串。

因此，问题简化为：寻找最小的字母集合 $X$，使得：

• $s[n-1] \in X$；
• 对每个长度为 $k$ 的窗口，$X$ 与该窗口的字母集合有交集。

集合覆盖的补集视角

记所有字母的全集为 $U = \{0,1,\dots,c-1\}$，用二进制掩码表示子集。对于每个窗口，计算该窗口内出现过的字母的掩码 $\text{win\_mask}$。条件 $X \cap \text{win\_mask} \neq \varnothing$ 等价于 $X \not\subseteq \overline{\text{win\_mask}}$，其中 $\overline{\text{win\_mask}} = U \setminus \text{win\_mask}$ 是窗口内未出现字母的集合。

因此，一个 $X$ 是“坏”的（即不满足条件）当且仅当存在某个窗口使得 $X \subseteq \overline{\text{win\_mask}}$，即 $X$ 是某个 $\overline{\text{win\_mask}}$ 的子集。我们只需要找出所有这样的坏 $X$，那么好的 $X$ 就是剩下的那些，并且还需要包含最后一个字符。

算法步骤

1. 特殊情况：若 $n < k$，则整个字符串可以作为一个单词，只需最后一个字符对应的格，答案为 $1$。

2. 预处理窗口：

   • 计算所有长度为 $k$ 的窗口的字母掩码。使用滑动窗口，维护每个字母在当前窗口中的出现次数和当前窗口的掩码，每次移动 $O(1)$ 更新。
   • 令 $\text{full} = (1 \ll c) - 1$。对每个窗口掩码 $m$，计算 $\text{comp} = \text{full} \oplus m$，并标记 $\text{bad}[\text{comp}] = 1$。

3. 子集传播（SOS DP）：

   • 对于每个 $i$ 从 $0$ 到 $c-1$，遍历所有掩码 $\text{mask}$ 从 $0$ 到 $\text{full}$，若 $\text{mask}$ 包含第 $i$ 位，则 $\text{bad}[\text{mask} \oplus (1 \ll i)] \mid= \text{bad}[\text{mask}]$。
   • 结束后，$\text{bad}[\text{mask}] = 1$ 当且仅当存在某个窗口的补集包含 $\text{mask}$，即 $\text{mask}$ 是某个 $\overline{\text{win\_mask}}$ 的子集，也就是 $\text{mask}$ 是坏的。

4. 寻找最小好集合：

   • 设 $\text{last} = 1 \ll (s[n-1] - \text{'A'})$。
   • 枚举所有掩码 $\text{mask}$，若 $\text{bad}[\text{mask}] = 0$ 且 $\text{mask} \& \text{last} \neq 0$，则 $\text{mask}$ 是一个可行的 $X$。记录其中 $\text{popcount}(\text{mask})$ 的最小值即为答案。

复杂度分析

• 滑动窗口计算所有窗口掩码：$O(n)$。
• SOS DP：$O(c \cdot 2^c)$。
• 枚举所有掩码：$O(2^c)$。
• 由于所有测试用例的 $n$ 之和 $\le 2^{18}$，所有 $2^c$ 之和 $\le 2^{18}$，总复杂度 $O\bigl((\sum n) + \max(c) \cdot 2^{18}\bigr)$，在 $c \le 18$ 时约为 $4.7 \times 10^6$，完全可行。

代码实现（C++）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        int n, c, k;
        cin >> n >> c >> k;
        string s;
        cin >> s;
        
        if (n < k) {
            // 整个字符串作为一个单词，只需最后一个字母
            cout << "1\n";
            continue;
        }
        
        int full = (1 << c) - 1;
        vector<int> bad(full + 1, 0);
        vector<int> cnt(c, 0);
        
        // 第一个窗口 [0, k-1]
        int win_mask = 0;
        for (int i = 0; i < k; ++i) {
            int ch = s[i] - 'A';
            if (cnt[ch] == 0) win_mask |= (1 << ch);
            cnt[ch]++;
        }
        int comp = full ^ win_mask;
        bad[comp] = 1;
        
        // 滑动窗口
        for (int i = k; i < n; ++i) {
            int left = s[i - k] - 'A';
            cnt[left]--;
            if (cnt[left] == 0) win_mask ^= (1 << left);
            
            int right = s[i] - 'A';
            if (cnt[right] == 0) win_mask |= (1 << right);
            cnt[right]++;
            
            comp = full ^ win_mask;
            bad[comp] = 1;
        }
        
        // SOS DP: 传播子集
        for (int i = 0; i < c; ++i) {
            for (int mask = 0; mask <= full; ++mask) {
                if (mask >> i & 1) {
                    bad[mask ^ (1 << i)] |= bad[mask];
                }
            }
        }
        
        int last_bit = 1 << (s.back() - 'A');
        int ans = c + 1;
        for (int mask = 0; mask <= full; ++mask) {
            if (!bad[mask] && (mask & last_bit)) {
                ans = min(ans, __builtin_popcount(mask));
            }
        }
        cout << ans << '\n';
    }
    
    return 0;
}