hdu 5651 xiaoxin juju needs help

xiaoxin juju needs help

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

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)

Recommend

wange2014 | We have carefully selected several similar problems for you: 5659 5658 5657 5654 5653

在网上找了模板，虽然我没有看懂，但是直接用了就过了。。。

题意：给你一个字符串，可以打乱顺序，问可以组合成几种回文串。

附上代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 const int mod=1e9+7;
 7 typedef long long ll;
 8 //返回d=gcd(a,b);和对应于等式ax+by=d中的x,y
 9 ll extend_gcd(ll a,ll b,ll &x,ll &y)
10 {
11     if(a==0&&b==0) return -1;//无最大公约数
12     if(b==0)
13     {
14         x=1;
15         y=0;
16         return a;
17     }
18     ll d=extend_gcd(b,a%b,y,x);
19     y-=a/b*x;
20     return d;
21 }
22 //*********求逆元素*******************
23 //ax = 1(mod n)
24 ll mod_reverse(ll a,ll n)
25 {
26     ll x,y;
27     ll d=extend_gcd(a,n,x,y);
28     if(d==1) return (x%n+n)%n;
29     else return -1;
30 }
31 
32 ll c(ll m,ll n)
33 {
34     ll i,j,t1,t2,ans;
35     t1=t2=1;
36     for(i=n; i>=n-m+1; i--) t1=t1*i%mod;
37     for(i=1; i<=m; i++) t2=t2*i%mod;
38     return  t1*mod_reverse(t2,mod)%mod;
39 }
40 
41 int main()
42 {
43     int T,i,j,n,m;
44     char ch[1005];
45     int a[30];
46     scanf("%d",&n);
47     while(n--)
48     {
49         memset(a,0,sizeof(a));
50         scanf("%s",ch);
51         for(i=0; ch[i]!=''; i++)
52             a[ch[i]-'a']++;
53         int t=0;
54         for(i=0; i<26; i++)
55         {
56             if(a[i]%2!=0)
57                 t++;
58             if(t>1)
59                 break;
60         }
61         if(i!=26)
62         {
63             printf("0
");
64             continue;
65         }
66         int len=strlen(ch);
67         ll sum=1;
68         len/=2;
69         for(i=0; i<26; i++)
70         {
71             sum=(sum*c(a[i]/2,len))%mod;
72             len-=a[i]/2;
73         }
74         printf("%d
",sum);
75     }
76     return 0;
77 }