在C++中查找作为字谜的回文数量

Question

我正在参加http://www.hackerrank.com上的在线编程竞赛.我正在研究的问题之一是找到一些字符串字符串的字谜.我已经解决了这个问题但是当我尝试上传它时,它在许多测试用例中都失败了.由于实际的测试用例对我来说是隐藏的,我不知道为什么它失败但我认为这可能是一个可扩展性问题.现在我不希望有人给我一个现成的解决方案,因为这不公平,但我只是好奇人们对我的方法的看法.

以下是该网站的问题描述:

既然国王知道如何找出一个给定的单词是否有一个回文或不回文的字谜,他就面临着另一个挑战.他意识到,对于给定的单词,可能存在多个字谜.你能帮他找出一个特定单词可能有多少字谜吗？

国王有很多话.对于每个给定的单词,国王需要找出作为回文的字符串的字符数.由于字谜的数量可能很大,国王需要字谜数%(10 ⁹ + 7).

输入格式:
包含输入字符串的单行

输出格式:
包含anagram字符串数的单行.palindrome % (109 + 7)

制约因素:

• 1<=length of string <= 105
• 字符串的每个字符都是小写字母.
• 每个测试用例至少有1个anagram,这是一个回文.

样本输入01:

aaabbbb

样品输出01:

3 

说明:
作为回文的给定字符串的三种排列可以作为abbabba,bbaaabb和bababab给出.

样本输入02:

cdcdcdcdeeeef

样本输出02:

90

如问题描述中所指定的,输入字符串可以大到10 ^ 5,因此大字符串的所有回文都是不可能的,因为我将遇到数字饱和度问题.此外,因为我只需要给出一个基于模(10 ^ 9 + 7)的模数答案,我想用基数(10 ^ 9 + 7)记录数字,并且在所有计算之后采用基数的分数部分(10 ^ 9) + 7)答案,因为那将是模数.

我的算法如下:

1. 存储每个字符的频率(只需要查看字符串的一半,因为后半部分应该与第一个字符串相同)
2. 如果有多个字符出现在奇数个时间,则不能使用回文
3. 否则每个char的频率递增计算回文数(动态编程)

对于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;
}

现在我花了很多时间在这个问题上,我只是想知道我的方法是否有问题,或者我在这里遗漏了一些东西.有任何想法吗？

Answer 1

请注意,字谜是反身的(它们从背面看起来与从正面看起来相同),因此每个字符出现的一半将在一侧,我们只需要计算这些字符的排列数.另一方面将完全颠倒这一方面,因此它不会增加可能性的数量.奇数出现的字符(如果存在)必须始终位于中间,因此在计算排列数时可以忽略它.

所以:

• 计算字符的频率

• 检查频率只有1个奇数

• 划分每个字符的频率(向下舍入 - 删除任何奇数事件).

• 使用以下公式计算这些字符的排列:(
  根据维基百科 - multiset排列)

  

由于上面的术语可能会变得很大,我们可能希望将公式分解为素数因子,这样我们就可以取消项,所以我们只剩下乘法,然后我相信我们可以在每次乘法之后,它应该适合于(因为).% 109 + 7long long(109+7)*105 < 9223372036854775807

感谢IVlad指出了一种比上面更有效的避免溢出的方法:

请注意,这是一个素数,所以我们可以使用费马的小定理来计算乘法逆,并乘以这些并在每一步取代而不是分割..通过平方使用取幂,这将非常快.p = 109 + 7mi mod pmi-1 = mi(10^9 + 5) (mod p)

我也发现了这个问题(也有一些有用的重复).

例子:

Input: aaabbbb

Frequency:
a  b
3  4

Div 2:
a  b
1  2

Solution:
3!/2!1! = 3

Input: cdcdcdcdeeeef

Frequency:
c  d  e  f
4  4  4  1

Div 2:
c  d  e  f
2  2  2  0

Solution:
6!/2!2!2!0! = 90

Answer 2

基本公式是:

p!/(a!*b!...*z!)

其中p是length/2单词的底板和a,b,c ..,z表示接受单词中出现频率a,b,c ...,z的一半的楼层.

现在剩下的唯一问题是如何计算.为此,检查这出.