C 操作集锦

题意

由小写英文字母组成的长度为n的一个字符串，求不相同的长度为k的子串的数量对1e9+7取模。
$1\le n\le 1e30\le k\le n$1≤n≤1e30≤k≤n

思路

$DP$DP 正难则反
正难则反，我们求所有不同的子串，不如把所有子串的数量求出来再减掉所以相同的子串数量。
若不去重求所有长度为k的子串的数量，则可由 $f\left[i\right]\left[j\right]=f[i-1]\left[j\right]+f[i-1][j-1]$f[i][j]=f[i−1][j]+f[i−1][j−1]推出到第 $i$i个数为止长度为 $j$j的子串数量。 $f[i-1]\left[j\right]$f[i−1][j]不难理解, $f[i-1][j-1]$f[i−1][j−1]代表的是到第 $i-1$i−1个数取了 $j-1$j−1个数再加上第s[i]个数构成了 $j$j个数。
本题的难点在于如何去重。我们观察一个字符串 $x...a_1...a_2$x...a1​...a2​。
发现如果以 $a$a结尾的长度 $j$j的字符串会在 $f\left[po{s}_{a\left[1\right]}\right]\left[j\right]=f[po{s}_{a1}-1]\left[j\right]+f[po{s}_{a\left[1\right]}-1][j-1]$f[posa[1]​][j]=f[posa1​−1][j]+f[posa[1]​−1][j−1]中计算一次以 $a_1$a1​为结尾的子串，而 $f\left[po{s}_{a\left[2\right]}\right]\left[j\right]=f[po{s}_{a2}-1]\left[j\right]+f[po{s}_{a\left[2\right]}-1][j-1]$f[posa[2]​][j]=f[posa2​−1][j]+f[posa[2]​−1][j−1]中又会计算一次以 $a_2$a2​为结尾的子串，那么就重复计算了前面的那部分以 $a1$a1为结尾的子串，显然后者包括前者且大于等于前者。
所以这里要用到 $pre\left[s\right[i\left]\right]$pre[s[i]]来记录上一个 $s\left[i\right]$s[i]所在的位置，当 pre[s[i]]>0时，即上一个 $s\left[i\right]$s[i]存在时，及时的减去上一个以 $f\left[pre\right[s\left[i\right]]-1][j-1]$f[pre[s[i]]−1][j−1]
坑点：注意k为0时答案为1(出题人说的），注意初始化。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 1e3+5;

ll n,k,pre[N],f[N][N];
char s[N];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>k;
	cin>>s+1;
	f[0][0]=1;
	for(int i=1;i<=n;i++){
		f[i][0]=1;
		for(int j=1;j<=i;j++){
			f[i][j]=f[i-1][j]+f[i-1][j-1];
			if(pre[s[i]]) f[i][j]-=f[pre[s[i]]-1][j-1];
			f[i][j]%=mod;
		}
		pre[s[i]]=i;
	}
	cout<<(f[n][k]+mod)%mod<<'\n';
	return 0;
}