传送门:牛客 - 练习赛60C
思路分析
dp[i][j]表示用前i个字符,组成长度为k的字符串数量
没有限制的话,转移就就是dp[i][j]=dp[i-1][j]+dp[i-1][j-1]
这样肯定有重复的,重复的部分就是dp[s[i]-‘a’-1][j-1],将这部分减掉就行了
样例输入
3 1
abc
样例输出
3
AC代码
#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <string>
#include <cstdio>
#include <chrono>
#include <random>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define sz(x) x.size()
#define lowbit(x) x&(-x)
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int INF = 0x3f3f3f3f;
const int N=1e3+10;
const int mod=1e9+7;
char s[N];
ll dp[N][N],pre[30];
int main() {
IOS;
#ifdef xiaofan
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int n,k;
cin>>n>>k;
cin>>s+1;
dp[0][0]=1;
for(int i=1;i<=n;i++){
dp[i][0]=1;
for(int j=1;j<=i;j++){
dp[i][j]=dp[i-1][j]+dp[i-1][j-1];
if(pre[s[i]-'a']) dp[i][j]-=dp[pre[s[i]-'a']-1][j-1];
dp[i][j]%=mod;
}
pre[s[i]-'a']=i;
}
cout<<(dp[n][k]+mod)%mod<<endl;
return 0;
}