题目链接：点击打开链接

题意：

给定长度为n的字符串s，常数k

显然s的子串一共同拥有 n(n-1)/2 个

要求找到一个长度为n的字符串t，使得t相应位置的k个子串字典序>s

#include<stdio.h>

#include<iostream>

#include<string.h>

#include<algorithm>

#include<vector>

#include<set>

using namespace std;

#define N 2505

#define mod 1000000007

#define ll __int64

ll n,k;

ll dp[N][N];//dp[i][j]表示i位置产生的j对（1-i-1都是同样的）

char s[N];

ll num[N], sum[N];

ll work(){

	if(k==0)return num[1];

	dp[0][0] = 1;

	sum[0] = 1;

	ll ans = 0;

	for(ll i = 1; i <= n; i++){

		ll len = n-i+1;

		for(ll j = 0; j <= k; j++) {

			for(ll z = i-1; z>=0 && (i-z)*len<=j; z--) {

				dp[i][j] = (dp[i][j]+dp[z][j-(i-z)*len])%mod;

			}

			dp[i][j] = dp[i][j]*('z'-s[i])%mod;

		}

		ans = (ans+dp[i][k]*num[i+1]%mod)%mod;

		for(ll j = 0; j <= k; j++) {

			dp[i][j] = (dp[i][j]+sum[j]*(s[i]-'a')%mod)%mod;

			sum[j] = (sum[j]+dp[i][j])%mod;

		}

	}

	return ans;

}

int main(){

	ll i;

	while(cin>>n>>k){

		cin>>s+1;

		num[n+1] = 1;

		for(i=n;i;i--)num[i] = num[i+1]*(s[i]-'a'+1)%mod;

		cout<<work()<<endl;

	}

	return 0;

}