C++14(g++5.4) 解法, 执行用时: 9ms, 内存消耗: 7268K, 提交时间: 2020-03-28 23:42:36

#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
char s[1000];
long long f[1005][1005], g[30]= {0};
int main() {
	int n, k;
	scanf("%d%d%s", &n, &k, s+1);
	for(int i=1; i<=n; i++) {
		f[i-1][0]=1;
		for(int j=1; j<=i; j++) {
			f[i][j]=(f[i-1][j]+f[i-1][j-1])%mod;
			if(g[s[i]]) f[i][j]-=f[g[s[i]]-1][j-1];
			f[i][j]=(f[i][j]+mod)%mod;
		}
		g[s[i]]=i;
	}
	f[n][0]=1;
	cout<<f[n][k]%mod<<endl;
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 12ms, 内存消耗: 8460K, 提交时间: 2020-03-28 17:39:48

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1010,mod=1e9+7;
int t,n,k; 
char s[N];
ll dp[N][N],f[N][30];
int main(){
	cin>>n>>k>>s+1;
	dp[0][0]=1;
	for(int i=1;i<=n;i++)
	{
		dp[i][0]=1;
		for(int j=1;j<=k;j++)
		{
			dp[i][j]=(dp[i-1][j]+dp[i-1][j-1]-f[j][s[i]-'a']+mod)%mod;
			f[j][s[i]-'a']=dp[i-1][j-1];
		}
	}
	ll ans=0;
	cout<<dp[n][k]; 
	return 0;
}