回文字符串
题目要求：
回文字符串是指从左到右和从右到左相同的字符串，现给定一个仅由小写字母组成的字符串，你可以把它的字母重新排列，以形成不同的回文字符串。 输入：非空仅由小写字母组成的字符串，长度不超过100； 输出：能组成的所有回文串的个数（因为结果可能非常大，输出对1000000007取余数的结果）。 例如：输入"aabb" 输出为2（因为“aabb”对应的所有回文字符串有2个：abba和baab） 函数头部 c: int palindrome(const char *s); c++ int palindrome(const string &s); java public static int palindrome(String s) ;
我的代码：
unsigned long long int jieceng(int n)
{
unsigned long long int result=1;
int i;
for (i = 1; i <= n; i++)
{
result*=i;
}
return result;
}
int palindrome(const char *s)
{
int len = strlen(s);
int num[26]={0};
int flag_len = len % 2;
int flag_bit;
int num_bit[26]={0};
int i;
int block = len/2;
unsigned long long int result;
int flag=0;
if (len > 100)
{
printf("Strings too long");
return 0;
}
for (i = 0; i < len; i++)
{
num[*(s+i)-'a']++; //统计出每个字母出现的个数
}
for (i = 0; i < 26; i++)
{
flag_bit = num[i] % 2;
if (flag_bit == 1)
{
flag++;
}
if ((flag_len == 0 && flag_bit == 1) || (flag_len == 1 && flag>1))
{
return 0;
}
num_bit[i] = num[i]/2;
}
result=jieceng(block);
for (i = 0; i < 26; i++)
{
if (num_bit[i]==0)
{
continue;
}
result=result/jieceng(num_bit[i]);
}
result=result%1000000007;
printf("Result is %d \n",result);
return result;
}
int _tmain(int argc, _TCHAR* argv[])
{
char str[101] = "hqaymehhrsfuqrpahrimsxftuxqrpsejouuehaqtsryxjhearxmogmi";
palindrome((const char *)(&str));
return 0;
}
其中一个问题就是计算大数的阶层时溢出的问题，比如我这个例子里面计算27!。现在64位最大就是long long int，表示不下。请问各位论坛的友友们，有没有什么方法去解决这个问题？
C++ 大数存储
[解决办法]
它不是说对1000000007取余数么……
别等算出来再取余，一边算一边砍
[解决办法]
这一题是求N!/(M1!*M2!*M3!*...*Mn！) % 1000000007的值。 其中M1+M2+...+Mn=N
你可以将分子1~N放入一个数组，再将分母1~M1 1~M2...1~Mn放入另一个数组，然后约掉分子分母所有能整除的，这时分母的数组里全是1，分母数组里一个一个乘，并且判断，一旦大于1000000007，立即%1000000007，最后就可以得到结果了。
[解决办法]
显然要用大数，用大数乘除法算出最后的值，然后用大数%计算1000000007
[解决办法]
（a*b）% n = (（a1+k1*n）*(b1 + k2*n))%n
= (a1*b1 + a1*k2*n + b1*k1*n + k1*k2*n*n)%n
= (a1*b1)%n
由定义知，a1 = a%n,b1 = b%n
所以（a*b）% n = ((a%n)*(b%n)) %n
所以在计算过程中，可以用1000000007取余，结果就不会大。
