這是 meelo 原創(chuàng)的 IEEEXtreme極限編程大賽題解
Xtreme 10.0 - N-Palindromes
題目來源 第10屆IEEE極限編程大賽
https://www.hackerrank.com/contests/ieeextreme-challenges/challenges/n-palindromes
Alice thinks that contest problem authors' obsession with palindromes is misplaced. She is much fonder of n-palindromes, which are words that are palindromes when the characters at exactly n positions are changed.
For example, Alice knows that her name (in lowercase) is a 2-palindrome, because she can create any of the following palindromes from her name by changing 2 characters: alila, acica, elile, ecice.
She also knows that her name is a 3-palindrome, because she can create palindromes by changing characters at 3 positions, e.g. ecace and zlilz. However, this is only a partial list, and she wants your help in determining the total number of such palindromes.
Note that the characters of an n-palindrome, including the n replacement characters, must all be lowercase English letters.
Input Format
The input starts with an integer t, on a line by itself, which gives the number of test cases.
Each test case is made up of an integer n followed by a lowercase string.
Constraints
1 ≤ t ≤ 20
1 ≤ n ≤ [length of string] ≤ 500
Output Format
For each test case, you should output, on a line by itself, the total number of palindromes that can be created by changing exactly n characters of the given string. Since this number may be very large, you should output the number modulo (109 + 7).
Sample Input
3
2 alice
1 racecar
3 alice
Sample Output
4
25
196
Explanation
The problem statement lists the four palindromes that can be made from the string alice, by changing 2 characters.
Since you can only change one character in racecar, you are constrained to changing the middle letter. This character can be changed to any of the 25 letters other than e.
For the last testcase, Alice has found that there are 196 palindromes that can be made from her name, by changing 3 characters.
題目解析
這是一道動態(tài)規(guī)劃的題鞋真，動態(tài)規(guī)劃的題一般都是要求一個超級大的數(shù)诅福。
關(guān)鍵是狀態(tài)怎么取。有3個關(guān)鍵的量決定結(jié)果的值扛伍。
可以修改的次數(shù)N，一定是一個決定狀態(tài)的變量。因為可以修改的次數(shù)不同礼患，結(jié)果一定不同。
一個長度為L的字符串，共有(L+1)//2對字符。如果所有的字母對都相同，則一定是回文串矛双。既然只與一對字母有關(guān)浅役，考慮問題的時候，總是考慮一對字母就好了拇惋。
共有(L+1)//2對字符，考慮一個子問題是從第1個字符算起的，前k對字符鸥鹉。這又是一個狀態(tài)變量。
斷定一個字符串是否是回文串庶骄，可以統(tǒng)計它不匹配的對數(shù)毁渗。如果不匹配的對數(shù)為0，則是回文串瓢姻。
剩余的一個狀態(tài)變量就是祝蝠，不匹配的對數(shù)b了。
狀態(tài)轉(zhuǎn)移方程幻碱。
有三種情況：
第1種绎狭，最特殊的一種，長度為奇數(shù)的字符串褥傍，考慮正中央的字符儡嘶。只有一個字符，一定是匹配的恍风”目瘢可以選擇修改，有25種修改的方法朋贬；或者不修改凯楔。
第2種，一對字符匹配锦募“谕停可以選擇修改，同樣有25種改法糠亩；或者不修改虐骑。
第3種，一對字符不匹配赎线。一定要修改才能成為回文串廷没。修改兩個字符有24種改法；只該一個字符有兩種改法垂寥，將一對字符的第2個改成第1個或者將第1個改成第2個颠黎。
考慮第3個樣例另锋，alice修改3次成為回文串。
f(3,3,2)=25f(2,2,2)+f(3,2,2)
=25(24f(0,1,1)+2f(1,1,1))+(24f(1,1,1)+2f(2,1,1))
=25(0+2(2f(0,0,0)))+(24(2f(0,0,0)+2(24f(0,0,0)))
=2522+242+242
=196
程序
C++
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
#define ll long long
#define MAX_LENGTH 510
#define MAX_N 1000000007
ll dp[MAX_LENGTH][MAX_LENGTH/2][MAX_LENGTH/2] = {0};
ll NPalindromes(const string &str, int N) {
int length = str.length();
int num_group = (length + 1) / 2; // number of pair
int num_mismatch = 0;
for(int i=0; i<num_group; i++) {
if(str[i] != str[length-i-1]) {
num_mismatch++;
}
}
dp[0][0][0] = 1;
// change n character
for(int n=0; n<=N; n++) {
// only consider first k character
for(int k=1; k<=num_group; k++) {
// exist b mismatch
for(int b=0; b<=num_mismatch; b++) {
if(k-1 == length-k) {
// odd string, considering middle character
dp[n][k][b] = dp[n][k-1][b];
if(n>=1) dp[n][k][b] = (dp[n][k][b] + 25 * dp[n-1][k-1][b]) % MAX_N;
}
else if(str[k-1] == str[length-k]) {
dp[n][k][b] = dp[n][k-1][b];
if(n>=2) dp[n][k][b] = (dp[n][k][b] + 25 * dp[n-2][k-1][b]) % MAX_N;
}
else if(str[k-1] != str[length-k]) {
if(b>=1 && n>=1) dp[n][k][b] = 2 * dp[n-1][k-1][b-1];
if(n>=2) dp[n][k][b] = (dp[n][k][b] + 24 * dp[n-2][k-1][b-1]) % MAX_N;
}
}
}
}
return dp[N][num_group][num_mismatch];
}
int main() {
int T;
cin >> T;
string str;
int n;
for(int t=0; t<T; t++) {
cin >> n >> str;
cout << NPalindromes(str, n) << endl;
}
return 0;
}
