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): 1202Accepted Submission(s): 344


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 integerT(T≤20)which represents the number of test cases.
For each test case, there is a single line containing a stringS(1≤length(S)≤1,000).

Output For each test case, print an integer which is the number of watermelon candies xiaoxin's leader needs to buy after mod1,000,000,007.

Sample Input

3 aa aabb a
Sample Output

1 2 1  

 

題意： 有一串字符 可以隨意交換每個字符的順序 輸出能組成的回文串的個數

 

注意的是 求排列組合的時候不能直接取模相除 會WA

首先統計每個字符出現的次數，然後在進行排列組合

#include
#include
#include
#include
#include
using namespace std;
const int mod=1e9+7;
typedef long long ll;
//返回d=gcd(a,b);和對應於等式ax+by=d中的x,y
ll extend_gcd(ll a,ll b,ll &x,ll &y)
{
    if(a==0&&b==0) return -1;//無最大公約數
    if(b==0){x=1;y=0;return a;}
    ll d=extend_gcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
//*********求逆元素*******************
//ax = 1(mod n)
ll mod_reverse(ll a,ll n)
{
    ll x,y;
    ll d=extend_gcd(a,n,x,y);
    if(d==1) return (x%n+n)%n;
    else return -1;
}

ll c(ll m,ll n)
{
	ll i,j,t1,t2,ans;
	t1=t2=1;
	for(i=n;i>=n-m+1;i--) t1=t1*i%mod;
	for(i=1;i<=m;i++) t2=t2*i%mod;
	return  t1*mod_reverse(t2,mod)%mod;
}
int main()
{
    int n;
    char ch[1010];
    int a[26];
    scanf("%d",&n);
    while(n--)
    {
        memset(a,0,sizeof(a));
        scanf("%s",ch);
        int len=strlen(ch);
        for(int i=0;i1)  //出現兩個奇數的字符則不可能組成回文串了  不需要判斷字符串長度是否為奇偶
        {
            printf("0\n");
        }
        else
        {
            ll ans=1;
            int sum=len/2;
            for(int i=0;i<26;i++)  //對每個字符進行位置的排列組合
            {
                if(a[i]&1) a[i]--;
                ans=(ans*c(a[i]/2,sum))%mod;  
                sum-=a[i]/2;
            }
            printf("%lld\n",ans);
        }
	}
 	return 0;
}