# Untitled

unknown
plain_text
2 years ago
1.3 kB
3
Indexable
Never
```#define mod 1000000007

long long dp[2222][2222];
char buf[2222];
string s;

long long sum1[2222];
long long sum2[2222][2222];

bool used[2222];

int Solution::solve(int A, int B, String C){
int n=A, k=B;
s = C;

dp[n][0] = 1;
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j <= k; j++) {
memset(used, false, sizeof(used));
dp[i][j] = (s[i] - 'a') * dp[i + 1][j];
if (j - (n - i) >= 0) dp[i][j] += ('z' - s[i]) * dp[i + 1][j - (n - i)];

for (int l = n - 1; l > i; l--) {
used[l] = true;
if ((n - l) * (l - i + 1) <= j)
dp[i][j] += ('z' - s[l]) * dp[l + 1][j - (n - l) * (l - i + 1)];
else
break;
}
for (int l = i + 1; l < n; l++) {
if (used[l]) break;
if ((n - l) * (l - i + 1) <= j)
dp[i][j] += ('z' - s[l]) * dp[l + 1][j - (n - l) * (l - i + 1)];
else
break;
}
dp[i][j] += sum1[j];
if (j == 0) dp[i][j]++;
dp[i][j] %= mod;

sum1[j] = (sum1[j] + (s[i] - 'a') * dp[i + 1][j]) % mod;
}
}
cout << dp[0][k] << endl;
return 0;
}```