大家好，又见面了，我是全栈君，祝每个程序员都可以多学几门语言。
题目链接：点击打开链接
题意：
给定长度为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;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/118439.html原文链接：https://javaforall.net
