这是 meelo 原创的 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.
题目解析
这是一道动态规划的题,动态规划的题一般都是要求一个超级大的数。
关键是状态怎么取。有3个关键的量决定结果的值。
可以修改的次数N,一定是一个决定状态的变量。因为可以修改的次数不同,结果一定不同。
一个长度为L的字符串,共有(L+1)//2对字符。如果所有的字母对都相同,则一定是回文串。既然只与一对字母有关,考虑问题的时候,总是考虑一对字母就好了。
共有(L+1)//2对字符,考虑一个子问题是从第1个字符算起的,前k对字符。这又是一个状态变量。
断定一个字符串是否是回文串,可以统计它不匹配的对数。如果不匹配的对数为0,则是回文串。
剩余的一个状态变量就是,不匹配的对数b了。
f(n,k,b)表示允许n次修改,只修改前k对字符,不匹配数为b时的回文串数。
状态转移方程为:
有三种情况:
第1种,最特殊的一种,长度为奇数的字符串,考虑正*的字符。只有一个字符,一定是匹配的。可以选择修改,有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)))
=25*2*2+24*2+24*2
=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/][MAX_LENGTH/] = {}; ll NPalindromes(const string &str, int N) {
int length = str.length();
int num_group = (length + ) / ; // number of pair
int num_mismatch = ;
for(int i=; i<num_group; i++) {
if(str[i] != str[length-i-]) {
num_mismatch++;
}
}
dp[][][] = ; // change n character
for(int n=; n<=N; n++) {
// only consider first k character
for(int k=; k<=num_group; k++) {
// exist b mismatch
for(int b=; b<=num_mismatch; b++) {
if(k- == length-k) {
// odd string, considering middle character
dp[n][k][b] = dp[n][k-][b];
if(n>=) dp[n][k][b] = (dp[n][k][b] + * dp[n-][k-][b]) % MAX_N;
}
else if(str[k-] == str[length-k]) {
dp[n][k][b] = dp[n][k-][b];
if(n>=) dp[n][k][b] = (dp[n][k][b] + * dp[n-][k-][b]) % MAX_N;
}
else if(str[k-] != str[length-k]) {
if(b>= && n>=) dp[n][k][b] = * dp[n-][k-][b-];
if(n>=) dp[n][k][b] = (dp[n][k][b] + * dp[n-][k-][b-]) % MAX_N;
}
}
}
} return dp[N][num_group][num_mismatch];
} int main() {
int T;
cin >> T;
string str;
int n; for(int t=; t<T; t++) {
cin >> n >> str;
cout << NPalindromes(str, n) << endl;
} return ;
}