HDU 5651

xiaoxin juju needs help
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)
문제 설명
xiaoxin 거 는 어 렸 을 때 부터 문자열 을 좋아 했 는데 6 학년 때 그 는 답장 꼬치 가 무엇 인지 알 게 되 었 다.이 때 xiaoxin 은 문자열 이 있다 면 
S
 답장 문자열 입 니 다. 이 문자열 은 앞으로 보 는 것 과 뒤에서 보 는 것 이 같 습 니 다.6 학년 여름방학 에 xiaoxin 은 곧 여름방학 숙제 를 마치 고 텐 센트 에 가서 인턴 을 하기 시작 했다.이날 leader 는 xiaoxin 에 게 문자열 을 주 었 습 니 다. xiaoxin 은 가능 한 모든 답장 문자열 을 만 드 는 함 수 를 써 주 십시오. 문자열 의 순 서 를 임의로 바 꿀 수 있 지만 어떤 문 자 를 버 릴 수 없습니다.그리고 leader 는 xiaoxin 에 게 서로 다른 답장 꼬치 를 만 들 때마다 수박 사탕 을 얻 을 수 있다 고 말 했다.xiaoxin 의 leader 는 수박 사탕 을 최대 몇 개 사 야 하 는 지 계산 해 주 시 겠 습 니까?
 
입력 설명
다 중 테스트 데이터.첫 줄 은 하나의 정 수 를 포함한다. 
T(T≤20) 조 수 를 나타 낸다.각 그룹의 테스트 데 이 터 는 소문 자 만 포함 하 는 문자열 을 보 여 줍 니 다. 
S(1≤length(S)≤1,000)  
출력 설명
각 조 의 테스트 데이터 에 대해 하나의 수 를 출력 하여 leader 가 사 야 할 수박 사탕 의 개 수 를 나타 내 는 결과 가 맞 았 다. 
1,000,000,007
 모형 을 뜨다.
 
입력 샘플
 
3
aa
aabb
a
 
출력 샘플
1
2
1
      고등학교 의 배열 과 조합 문제, C (m, n) = C (m - 1, n - 1) + C (m, n - 1) (n > = m - 1).직접 계산 하면 64 가 터 지 는데 최 악의 경 우 는 C (250, 500) 이기 때문에 모델 링 을 한다. 

#include<stdio.h>
#include<string.h>
int main()
{
    __int64 n,i,j,a[28],b[505][505],sum1,sum2;
    __int64 sum;
    char str[1005]; 
    memset(b,-1,sizeof(b));
    scanf("%I64d",&n);
    for(j=0;j<501;j++)
        b[0][j]=1;
    for(j=1;j<501;j++)
        b[1][j]=j;
    for(i=2;i<=501;i++){
        for(j=i;j<=501;j++){
            if(i==j)b[i][j]=1;
            else b[i][j]=(b[i-1][j-1]+b[i][j-1])%1000000007;
        }//  C(m,n)
    }
    for(i=0;i<n;i++){
        scanf("%s",str);
        memset(a,0,sizeof(a));
        int ls=strlen(str);
        for(j=0;j<ls;j++){
            a[str[j]-'a'+1]++;
        }
        sum1=sum2=0;
        for(j=1;j<=26;j++){
            if(a[j]%2==0)sum1++;
            else sum2++;
        }
        if(sum2>1)sum=0;//           2 ，            
        else{
            sum=1;
            int k=ls/2,ok=0;
            for(j=1;j<=26;j++){
                if(a[j]>0){
                    sum=(sum*b[a[j]/2][k])%1000000007;
                    k-=a[j]/2;//      
                }
            }
        }
        if(ls==1)sum=1;//        ，      
        if(sum2==1&&ls%2==0)sum=0;//                   ，           
        printf("%I64d
",sum);
    }
    return 0;
}