HDU 5651 计算回文串个数问题(有重复的全排列、乘法逆元、费马小定理)

原题：

http://acm.hdu.edu.cn/showproblem.php?pid=5651

很容易看出来的是，如果一个字符串中，多于一个字母出现奇数次，则该字符串无法形成回文串，因为不能删减字母。
当能构成回文串时，我们只需考虑这个回文串左半部分的情况，所以这个问题也就变成了求一半字符串的有重复的全排列。
因为应用全排列公式中，会用大数除以大数再取余，除法不能简单的分子、分母取余再做除法，这时就要用到乘法逆元，同时用费马小定理求乘法逆元
相关公式：http://www.cnblogs.com/i2u9/p/full_seq.html
乘法逆元及其证明：http://www.cnblogs.com/tiankonguse/archive/2012/08/14/2638949.html

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define maxn 1111
 4 #define mod 1000000007
 5 char s[maxn];
 6 int book[30];//记录每个字母出现次数 
 7 long long fact[maxn];//计算保存阶乘 
 8 //求快速幂 
 9 long long fpow(long long a,long long b){
10     long long res = 1;
11     while(b){
12         if(b&1)
13             res = res*a%mod;
14         b >>= 1;
15         a = a*a%mod;
16     }
17     return res;
18 }
19 int main(){
20     //计算阶乘，全排列用 
21     fact[0] = 1;
22     for(int i = 1;i<maxn;i++)
23         fact[i] = fact[i-1]*i%mod;
24     int t;
25     scanf("%d",&t);
26     while(t--){
27         memset(book,0,sizeof(book));
28         scanf(" %s",s);
29         for(int i = 0;s[i];i++){
30             book[s[i]-'a']++;
31         }
32         int cnt = 0;//计算出现奇数次字母的个数 
33         for(int i= 0;i<27;i++){
34             if(book[i]&1)
35                 cnt++;
36             book[i] /= 2; 
37         }
38         int len = strlen(s);
39         if(cnt >1){
40             puts("0");
41         }else{
42             long long ans = fact[len/2];
43             for(int i = 0;i<26;i++)
44                 if(fact[book[i]])
45                     ans = ans*fpow(fact[book[i]],mod-2)%mod;
46             printf("%I64d
",ans);
47         }
48     }
49     return 0;
50 }

HDU 5651 计算回文串个数问题(有重复的全排列、乘法逆元、费马小定理)

相关推荐