子序列中的 k 种字母
https://kamacoder.com/problempage.php?pid=1028
#include<iostream>
#include<string>
#include<vector>
#include<cmath>
using namespace std;
#define mod 1000000007
int main()
{
int n=0;
int k=0;
cin>>n>>k;
string s;
cin>>s;
vector<int>hash(26,0);
for(int i = 0; i < n; i++){
hash[s[i]-'a']++;
}
//dp[j] 表示选择 j 个字符的组合数量。
vector<long long>dp(k+1);
dp[0]=1;
for(int i=0;i<26;i++)
{
//对于每个小写字母(共 26 种),计算其对应的贡献x
int x=((long long)pow(2,hash[i])%mod-1);//因为每个字符可以选择 0 到 hash[i] 次,选与不选就是pow(2,hash[i])-1
for(int j=k;j>=1;j--)
{
dp[j]=dp[j]+dp[j-1]*x;//在已经选择了 j-1 个字符的前提下,考虑添加当前字符的组合方式
dp[j]=dp[j]%mod;//将结果对 mod 取余,以防止整数溢出
}
}
cout<<dp[k]<<endl;
}