时间限制：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表示以什么字母结尾，（因为我们可以将a~z转换成数字，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(26n2)
我们这次把26给省掉变成O（n2）
设两个数组
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;
}
京公网安备 11010502036488号