我正在参加http://www.hackerrank.com上的在线编程竞赛。我正在研究的问题之一是找到一个字符串的回文数。我已经解决了这个问题，但是当我尝试上传它时，它在许多测试用例中都失败了。由于实际的测试用例对我来说是隐藏的，我不确定它为什么会失败，但我认为这可能是一个可扩展性问题。现在我不希望有人给我一个现成的解决方案，因为这不公平，但我只是好奇人们对我的方法的看法。
以下是网站上的问题描述：
现在国王知道如何找出一个给定的单词是否有一个回文的字谜，他面临着另一个挑战。他意识到对于一个给定的单词，可以有不止一个字谜。你能帮他找出一个给定的回文单词有多少字谜？
国王有很多话。对于每个给定的单词，国王需要找出字符串中作为回文的字谜的数量。由于字谜的数量可能很大，因此国王需要字谜的数量％（10 9 + 7）。
输入格式：
包含输入字符串的单行输出格式：
单行包含.palindrome % (109 + 7)约束：
1<=length of string <= 105- 字符串的每个字符都是一个小写字母。
- 每个测试用例至少有 1 个回文字谜。
样本输入 01：
aaabbbb样本输出 01：
3解释：
给定字符串的三个排列是回文，可以给出为 abbabba 、 bbaaabb 和 bababab。样本输入 02：
cdcdcdcdeeeef样本输出 02：
90
正如问题描述中所指定的，输入字符串可以大到 10^5，因此大字符串的所有回文都是不可能的，因为我会遇到数字饱和问题。此外，由于我只需要给出一个基于模 (10^9 + 7) 的答案，我想到了以 (10^9 + 7) 为基数的数字的对数，并且在所有计算之后以 (10^9) 为基数的分数部分的反对数+ 7) 的答案，因为无论如何这都是模数。
我的算法如下：
- 存储每个字符的频率（只需要查看字符串的一半，因为后半部分应该与回文的 def 的第一个相同）
- 如果出现多个奇数次的字符，则不可能出现回文
- 否则对于每个字符的频率增量计算回文数（动态编程）
对于 DP，以下是子问题：previous_count = 1
每增加一个字符
added number of palindromes = previous_count * (number_of_char_already_seen + 1)/(number of char same as current char)
这是我的代码：
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <fstream>
using namespace std;
#define MAX_SIZE 100001
void factorial2 (unsigned int num, unsigned int *fact) {
fact[num]++;
return;
}
double mylog(double x) {
double normalizer = 1000000007.0;
return log10(x)/log10(normalizer);
}
int main() {
string in;
cin >> in;
if (in.size() == 1) {
cout << 1 << endl;
return 0;
}
map<char, int> freq;
for(int i=0; i<in.size(); ++i) {
if (freq.find(in.at(i)) == freq.end()) {
freq[in.at(i)] = 1;
} else {
freq[in.at(i)]++;
}
}
map<char, int> ::iterator itr = freq.begin();
unsigned long long int count = 1;
bool first = true;
unsigned long long int normalizer = 1000000007;
unsigned long long int size = 0;
unsigned int fact[MAX_SIZE] = {0};
vector<unsigned int> numerator;
while (itr != freq.end()) {
if (first == true) {
first = false;
} else {
for (size_t i=1; i<=itr->second/2; ++i) {
factorial2(i, fact);
numerator.push_back(size+i);
}
}
size += itr->second/2;
++itr;
}
//This loop is to cancel out common factors in numerator and denominator
for (int i=MAX_SIZE-1; i>1; --i) {
while (fact[i] != 0) {
bool not_div = true;
vector<unsigned int> newNumerator;
for (size_t j=0; j<numerator.size(); ++j) {
if (fact[i] && numerator[j]%i == 0) {
if (numerator[j]/i > 1)
newNumerator.push_back(numerator[j]/i);
fact[i]--; //Do as many cancellations as possible
not_div = false;
} else {
newNumerator.push_back(numerator[j]);
}
}
numerator = newNumerator;
if (not_div) {
break;
}
}
}
double countD = 0.0;
for (size_t i=0; i<numerator.size(); ++i) {
countD += mylog(double(numerator[i]));
}
for (size_t i=2; i <MAX_SIZE; ++i) {
if (fact[i]) {
countD -= mylog((pow(double(i), double(fact[i]))));
fact[i] = 0;
}
}
//Get the fraction part of countD
countD = countD - floor(countD);
countD = pow(double(normalizer), countD);
if (floor(countD + 0.5) > floor(countD)) {
countD = ceil(countD);
} else {
countD = floor(countD);
}
count = countD;
cout << count;
return 0;
}
现在我在这个问题上花了很多时间，我只是想知道我的方法是否有问题，或者我在这里遗漏了什么。有任何想法吗？
