写出宝石排列问题的C++代码

宝石排列问题（Gem Combination Problem）是一个经典的组合问题，题目描述如下：

给定一个由小写字母组成的字符串 S，求出其中长度为恰好 k 的子串有多少种不同的排列方法，即如果两个子串的字母种类和数量都相同，则它们被认为是相同的排列。

下面是一份用 C++ 编写的解答代码：

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

const int MAXN = 1e5 + 5;

int n, k;
char s[MAXN];
int cnt[26];
int f[MAXN];

int main() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    scanf("%d", &k);
    for(int i = 1; i <= n; i++) cnt[s[i] - 'a']++;
    f[0] = 1;
    for(int i = 0; i < 26; i++) {
        for(int j = n; j >= cnt[i]; j--) {
            f[j] += f[j - cnt[i]];
        }
    }
    int ans = 0;
    for(int i = k; i <= n; i++) ans += f[i];
    printf("%d\n", ans);
    return 0;
}

该代码的核心思路是利用动态规划求解方案数。具体来说，我们定义 $f(i)$ 表示选出 $i$ 个字母的方案数，最终的答案即为 $\sum_{i=k}^n f(i)$。

对于每个字母 $c$，可以将 $f(i)$ 转移为 $f(i-cnt_c)$，其中 $cnt_c$ 表示字符串 $S$ 中字母 $c$ 出现的次数。这样一来，我们就可以用简单的循环枚举字母和方案数，将时间复杂度优化到 $O(n)$。

需要注意的是，为了保证排列的唯一性，我们需要对答案求和时只考虑长度为 $k$ 的子串，而不是所有长度大于等于 $k$ 的子串。