子序列中的 k 种字母
https://kamacoder.com/problempage.php?pid=1028
#include<iostream>
#include<string>
#include<vector>
#include<cmath>
using namespace std;
#define mod 1000000007int 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 种),计算其对应的贡献xint x=((long long)pow(2,hash[i])%mod-1);//因为每个字符可以选择 0 到 hash[i] 次,选与不选就是pow(2,hash[i])-1for(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;
}