操作集锦
- 比赛主页
- 我的提交
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
有一款自走棋有26种操作,每种操作我们都用a,b,c,d,...,x,y,za,b,c,d,...,x,y,z的符号来代替.
现在牛牛有一个长度为nn的操作序列,他现在可以从里面拿出某些操作来组合成一个操作视频, 比如说操作序列是abcdabcd,那么操作视频就有a,b,c,d,ab,ac,ada,b,c,d,ab,ac,ad等(也就是操作序列的子序列).他现在想知道长度为kk且本质不同的操作视频有多少种.
比如对于abababab，长度为22且本质不同的结果有ab,aa,ba,bbab,aa,ba,bb。
考虑到答案可能非常大,你只需要输出在模1e9+71e9+7意义下的答案就可以了.
输入描述:第一行两个整数n,kn,k.
第二行一个长度为nn的字符串,保证只存在小写字母.
输出描述:一行一个整数表示长度为kk且本质不同的操作视频的个数.
示例1
输入复制
3 1 abc输出
复制
3备注:
1≤n≤1e31≤n≤1e3
0≤k≤n0≤k≤n
const int MAX=1010;
const int MOD=1e9+7;
int n,k;
char s[MAX];
int ch[MAX][30];
int dp[MAX][MAX];
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-1]+dp[i-1][j]-ch[j][s[i]-'a'])%MOD;
ch[j][s[i]-'a']=dp[i-1][j-1];
}
}
cout<
