Untitled
unknown
plain_text
3 years ago
1.3 kB
7
Indexable
#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; }
Editor is loading...