xiaoxin juju needs help

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

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

aabb

Sample Output

排列组合问题。C[n][m]用dp求一下。

然后对于aabababbcc这组样例我们取1/2进行考虑，aabbc. 答案就是c(5,2)*c(3,2)*c(1,1)

/* ***********************************************

Author        :

Created Time  :2016/3/30 15:28:22

File Name     :hdu5651.cpp

************************************************ */

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <stdio.h>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <iomanip>

#include <list>

#include <deque>

#include <stack>

#define ull unsigned long long

#define ll long long

#define mod 1000000007

#define INF 0x3f3f3f3f

#define maxn 10010

#define cle(a) memset(a,0,sizeof(a))

const ull inf = 1LL << ;

const double eps=1e-;

using namespace std;

priority_queue<int,vector<int>,greater<int> >pq;

struct Node{

    int x,y;

};

struct cmp{

    bool operator()(Node a,Node b){

        if(a.x==b.x) return a.y> b.y;

        return a.x>b.x;

    }

};

bool cmp(int a,int b){

    return a>b;

}

char s[maxn];

int cnt[];

int c[][];

void init(){

    memset(c,,sizeof c);

    for(int i=;i<;i++){

        c[i][]=i;c[i][]=;

    }

    for(int i=;i<=;i++){

        for(int j=;j<=i;j++){

            c[i][j]=(c[i-][j-]+c[i-][j])%mod;

        }

    }

}

void solve(int n){

    n/=;

    ll ans=,sum=n;

    for(int i=;i<;i++){

        ans*=c[n][cnt[i]/];

        ans%=mod;

        n-=cnt[i]/;

    }

    cout<<ans<<endl;

}

int main()

{

    #ifndef ONLINE_JUDGE

    freopen("in.txt","r",stdin);

    #endif

    //freopen("out.txt","w",stdout);

    int t;

    cin>>t;

    init();

    while(t--){

        scanf("%s",&s);

        cle(cnt);

        int n=strlen(s);

        for(int i=;i<n;i++){

            cnt[int(s[i]-'a')]++;

        }

        int mark=;

        for(int i=;i<;i++){

            if(cnt[i]&){

                mark++;

            }

        }

        if(n%==){

            if(mark>){

                printf("%d\n",);continue;

            }

            solve(n);

        }

        else{

            if(mark==){

                solve(n);

            }

            else{

                printf("%d\n",);

            }

        }

    }

    return ;

}

巴特西

HDU 5651xiaoxin juju needs help

xiaoxin juju needs help

最新文章

热门文章