2021-09-07百度后端笔试第三题（好题！！！！！

题目描述

给定一个长度为的字母序列，求包含恰好有种字母的子序列的数量，答案对取模。
例如：

输入
6 5
eecbad
输出
3
输入
10 2
aaaccebecd
输出
126

思路

个人觉得这个是个极好的题，我们发现对于每个字母的贡献考虑组合数，设字母出现的次数是，那么贡献就是(因为)，所以我们可以类比背包问题，将这个贡献当作价值，重量赋为，背包容量是，令表示取种字母的方案数，从而求解。

代码

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

const int N = 1e5 + 5;
long long dp[26];
const long long mod = 1e9 + 7;
char s[N];
long long qpow(long long a, long long b)
{
    long long res = 1;
    while (b)
    {
        if (b & 1)
        {
            res = res * a % mod;
        }
        b /= 2;
        a = a * a % mod;
    }
    return res;
}
int v[30],w[30];
int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    scanf("%s", s + 1);
    map<char, int> mp;
    for (int i = 1; i <= n; i++)
        mp[s[i]]++;
    for (char i = 'a'; i <= 'z'; i++)
    {
        v[i - 'a'] = qpow(2, mp[i]) - 1;
        w[i - 'a'] = 1;
    }
    dp[0] = 1;
    for (int i = 0; i < 26; i++)
    {
        for (int j = k; j >= 1; j--)
        {
            if (j >= w[i])
            {
                dp[j] = (dp[j] + dp[j - w[i]] * v[i]) % mod;
            }
        }
    }

    cout << dp[k] << endl;
    return 0;
}