HDU 5651 逆元

xiaoxin juju needs help

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 809 Accepted Submission(s): 231

Problem Description

As we all known, xiaoxin is a brilliant coder. He knew **palindromic** strings when he was only a six grade student at elementry school.

This summer he was working at Tencent as an intern. One day his leader came to ask xiaoxin for help. His leader gave him a string and he wanted xiaoxin to generate palindromic strings for him. Once xiaoxin generates a different palindromic string, his leader will give him a watermelon candy. The problem is how many candies xiaoxin's leader needs to buy?

Input

This problem has multi test cases. First line contains a single integer

Output

For each test case, print an integer which is the number of watermelon candies xiaoxin's leader needs to buy after mod

Sample Input

aabb

Sample Output

Source

BestCoder Round #77 (div.2)

题意：给一段只有小写字母的字符串判断能够组合成多少种回文串

题解：首先，如果不止一个字符出现的次数为奇数，则结果为0。否则，我们把每个字符出现次数除2，也就是考虑一半的情况。那么结果就是这个可重复集合的排列数了。

A!/(n1！*n2！....)

这里直接除会出错需要用到逆元的知识

http://blog.csdn.net/acdreamers/article/details/8220787

另外如何求逆元？

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<map>
 5 #define ll __int64
 6 using namespace std;
 7 int n;
 8 char a[1005];
 9 #define mod 1000000007
10 map<char,int> mp;
11 ll quickmod(ll a,ll b)
12 {
13     ll sum=1;
14     while(b)
15     {
16         if(b&1)
17             sum=(sum*a)%mod;
18         b>>=1;
19         a=(a*a)%mod;
20     }
21     return sum;
22 }
23 
24 int main()
25 {
26     scanf("%d",&n);
27     for(int i=1;i<=n;i++)
28     {
29         mp.clear();
30         int jishu=0;
31         int sum=0;
32         scanf("%s",a);
33         int len=strlen(a);
34         for(int j=0;j<len;j++)
35             mp[a[j]]++;
36         for(int j='a';j<='z';j++)
37         {
38             if(mp[j]%2==1)
39              {
40              jishu++;
41              }
42         }
43         if(len%2==0)
44         {
45             if(jishu!=0)
46             {
47             cout<<"0"<<endl;
48             continue;}
49         }
50         else
51         {
52             if(jishu>1)
53             {cout<<"0"<<endl;
54             continue;}
55         }
56       for(int j='a';j<='z';j++)
57       {
58            sum=sum+mp[j]/2;
59       }
60       ll ans=1;
61       ll gg=1;
62       for(int j='a';j<='z';j++)
63       {
64       for(int k=1;k<=mp[j]/2;k++)
65          gg=gg*k%mod;
66 
67       }
68       for(int j=1;j<=sum;j++)
69       {
70           ans=ans*j%mod;
71       }
72       printf("%I64d
",(ans*(quickmod(gg,mod-2)%mod))%mod);
73     }
74     return 0;
75 }

View Code