题目传送

时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format:
%lld

题目描述

有一款自走棋有26种操作,每种操作我们都用a,b,c,d,...,x,y,z的符号来代替.
现在牛牛有一个长度为nnn的操作序列,他现在可以从里面拿出某些操作来组合成一个操作视频,
比如说操作序列是abcdabcdabcd,那么操作视频就有a,b,c,d,ab,ac,ad等(也就是操作序列的子序列).他现在想知道长度为k且本质不同的操作视频有多少种.
比如对于abab，长度为2且本质不同的结果有ab,aa,ba,bb 考虑到答案可能非常大,你只需要输出在模1e9+7意义下的答案就可以了.

输入描述:

第一行两个整数n,k 第二行一个长度为n的字符串,保证只存在小写字母.

输出描述:

一行一个整数表示长度为k且本质不同的操作视频的个数.

示例1
输入

3 1
abc

输出

3

备注:

1≤n≤1e3
0≤k≤n
题意：
给你一个长度为n的字符串，问有多有长度为k的子字符串，且不重复。
题解：
这种求子字符串数量题一般都用dp来做
dp[i][j]表示q前i个字符串中，长度为j的子字符串的数量
但是这个题是存在重复情况的，我们还要进行去重
这咋整？我们将dp从二维增加到三维，dp[i][j][k]新填一个k，k表示以什么字母结尾，（因为我们可以将az转换成数字，a对应0，b对应1，一次类推），在dp添加时我们if判断，如果当前结尾不是我们指定的字母，就不添加当前这位；如果是的话，就在前面的基础在最后一位填上这个字母。
不明白？很正常（笑哭），我也快把自己讲晕了~~
这个k就相当于是针对性的，dp[i][j][k]就是前i个字符串中选j个以k为结尾的字符数量
举例大法：n=4 m=2
abab
在这里插入图片描述
你会发现链接对于abab，长度为2且本质不同的结果有ab,aa,ba,bb，虽然abab的子字符串中ab出现两次，但是只统计了一次，因为在算以b（最后这个b）为结尾的时候，前面两个a算作一个a处理
代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1004;
int dp[maxn][maxn][30];
char a[maxn];
const int mod=1e9+7;
long long sum=0;
int main()
{
    int n,m;
    cin>>n>>m;
    char ch=getchar();
    cin>>a;
    if(m==0){
        cout<<1;
        return 0;
    }
    for(int i=1;i<=n;i++)
    {
        dp[i][1][a[i-1]-'a']=1;
        for(int j=1;j<=m;j++)
        {
            for(int w=0;w<=25;w++)
            {
                if(a[i-1]-'a'==w)
                {
                    for(int k=0;k<=25;k++)
                    {
                        dp[i][j][w]=(dp[i][j][w]+dp[i-1][j-1][k])%mod;
                    }

                }
                    else dp[i][j][w]=(dp[i][j][w]+dp[i-1][j][w])%mod;
            }

        }
    }
    for(int i=0;i<=25;i++)
    sum=(sum+dp[n][m][i])%mod;
    cout<<sum;
}

注意注意：不要忘了MOD
据说还能优化，等学会了再更新

啦啦啦我又回来了

在从别人那里学习完之后
上面这个解法复杂度是O(26n^2^)
我们这次把26给省掉变成O（n^2^）
设两个数组
g[i]：在前i个字符长度为j的本质不同的子序列个数
f[i][j]:前i个字符长度为j的本质不同的子序列个数
f[i][j]=f[i-1][j-1]+f[i-1][j]
f[i-1][j-1]就是不选择s[i]
f[i-1][j]就是选择s[i]
选择的s[i]加上后有可能会重复，就需要我们先判断当前的s[i]是否用过，然后把重复的部分去掉
f [ i ] [ j ] =f[ i ] [ j ]-f[ g [ s [ i ] ] - 1 ] [ j - 1 ]
还有在加的过程中注意不断的mod

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int mod=1e9+7;

char s[100005];
LL  f[1005][1005], g[30]={0};
int main() {

    int n, k;
    scanf("%d%d", &n, &k);
    scanf("%s", 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;
}

完毕撒花✿✿ヽ(°▽°)ノ✿