HDU 5651 xiaoxin juju needs help(BestCoder Round #77 (div.1)1001)

传送门

xiaoxin juju needs help

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 861    Accepted Submission(s): 243

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 T(T≤20) which
represents the number of test cases.

For each test case, there is a single line containing a string S(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 mod 1,000,000,007.

Sample Input

3
aa
aabb
a

Sample Output

1
2
1

Source

BestCoder Round #77 (div.2)

题目大意:

xiaoxin巨从小就喜欢字符串,六年级的时候他就知道了什么是回文串。这时,xiaoxin巨说到:如果一个字符串 SS 是回文串,那么该字符串从前往后看和从后往前看是一样一样的。

六年级的暑假,xiaoxin很快就做完了暑假作业,然后到腾讯做起了实习生。这日,leader给了xiaoxin一个字符串,请xiaoxin帮忙写一个函数来生成所有可能的回文串,可以任意改变字符串的顺序但是不可以扔掉某个字符。并且leader告诉xiaoxin,每生成一个不一样的回文串就可以得到一颗西瓜糖。

请你帮忙计算xiaoxin的leader最多需要买多少颗西瓜糖呢?

解题思路:

回文字符串的个数可以根据一个公式来推导一下:

条件:

1.len = strlen(str),len>>=1;

2.num[i]:表示的是字符串每个字符 -  ‘a‘ 的个数,然后将其除以2;

结果: ret  =  (len!)/(num[0]! * num[1]! * ... * num[25]!)  MOD 1e9+7;

根据这个公式我们只需要求一下阶乘的逆元就行了,因为是取模的运算,所以我们一边乘一边取模,不会超long long,最后不要忘记的是,如果是负数要转化为正数在进行取模,最后就是乘起来就行了。。。

My Code:

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long LL;
const int MOD = 1e9+7;
const int MAXN = 1e3+5;
char str[MAXN];
int num[28];
LL a[28];
void Ex_gcd(LL a, LL b, LL &x, LL &y)
{
    if(b == 0)
    {
        x = 1;
        y = 0;
        return;
    }
    LL x1, y1;
    Ex_gcd(b, a%b, x1, y1);
    x = y1;
    y = x1-(a/b)*y1;
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        cin>>str;
        int len = strlen(str);
        memset(num, 0, sizeof(num));
        for(int i=0; i<len; i++)
            num[str[i]-'a']++;
        int sum = 0;
        for(int i=0; i<26; i++)
            if(num[i]%2)
                sum++;
        if(sum >= 2)
            puts("0");
        else
        {
            LL ret = 1;
            len>>=1;
            for(int i=0; i<26; i++)
            {
                LL x, y;
                num[i]>>=1;
                a[i] = 1;
                for(int j=1; j<=num[i]; j++)
                    a[i] = a[i]*j%MOD;
                Ex_gcd(a[i], MOD, x, y);
                x = (x%MOD+MOD)%MOD;
                a[i] = x;
            }
            for(int i=1; i<=len; i++)
                ret = ret*i%MOD;
            for(int i=0; i<26; i++)
                ret = ret*a[i]%MOD;
            printf("%lld\n",ret%MOD);
        }
    }
    return 0;
}
时间: 03-25

HDU 5651 xiaoxin juju needs help(BestCoder Round #77 (div.1)1001)的相关文章

HDU 5651 xiaoxin juju needs help 逆元

给你n个字母,求可以组成的回文串的个数 1.n为奇数,有一个字母的个数为奇数 2.n为偶数,字母个数全为偶数 然后将字母的个数num[i]/2,得出在对称轴左边的个项字母的个数 假设左边有len个字母,如果每个字母都不同则有len!中可能 然后除去所有重复的可能num[i]!即可 因为除法取模 (len!/num[i]!)%mod a^(p-1) = 1(mod p)p为素数    于是 a*a^(p-2) = 1(mod p)所以a^(p-2)替代1/a. 所以上面的公式  ->  len!*

ACM学习历程—HDU5585 Numbers(数论 || 大数)(BestCoder Round #64 (div.2) 1001)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5585 题目大意就是求大数是否能被2,3,5整除. 我直接上了Java大数,不过可以对末尾来判断2和5,对所有位的和来判断3. 代码就不粘了.

hdu 5171 GTY&#39;s birthday gift (BestCoder Round #29)

GTY's birthday gift                                                                       Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 209    Accepted Submission(s): 71 Problem Description F

BestCoder Round #69 (div.2) Baby Ming and Weight lifting(hdu 5610)

Baby Ming and Weight lifting Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 681    Accepted Submission(s): 280 Problem Description Baby Ming is fond of weight lifting. He has a barbell pole(the

HDU 5671 Matrix (BestCoder Round #81 (div.2) 1002)

传送门 Matrix Time Limit: 3000/1500 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 311    Accepted Submission(s): 142 Problem Description There is a matrix M that has n rows and m columns (1≤n≤1000,1≤m≤1000).Then we

BestCoder Round #11 (Div. 2) 前三题题解

题目链接: huangjing hdu5054 Alice and Bob 思路: 就是(x,y)在两个參考系中的表示演全然一样.那么仅仅可能在这个矩形的中点.. 题目: Alice and Bob Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 216    Accepted Submission(s): 166 Problem De

hdu5418 BestCoder Round #52 (div.2) Victor and World ( floyd+状压dp)

Problem Description After trying hard for many years, Victor has finally received a pilot license. To have a celebration, he intends to buy himself an airplane and fly around the world. There are n countries on the earth, which are numbered from 1 to

BestCoder Round #11 (Div. 2) 题解

HDOJ5054 Alice and Bob Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 302    Accepted Submission(s): 229 Problem Description Bob and Alice got separated in the Square, they agreed that if they

BestCoder Round #50 (div.2)

题目传送:BestCoder Round #50 (div.2) BC感觉越做越无语了 1001.Distribution money AC代码: #include <map> #include <set> #include <list> #include <cmath> #include <deque> #include <queue> #include <stack> #include <bitset> #