xiaoxin jujuju needs help hdu (5651) 양 휘 삼각형 과 이 항 식

7475 단어
xiaoxin juju needs help  
 Accepts: 150
 
 Submissions: 966
 Time Limit: 2000/1000 MS (Java/Others)
 
 Memory Limit: 65536/65536 K (Java/Others)
문제 설명
xiaoxin         ,                 。  ,xiaoxin   :        SS     ,                       。

      ,xiaoxin          ,           。  ,leader  xiaoxin     , xiaoxin                  ,                       。  leader  xiaoxin,                      。

      xiaoxin leader            ?

입력 설명
T(T\leq 20)T(T20)S(1\leq length(S)\leq 1,000)S(1length(S)1,000)

출력 설명
        ,     ,   leader          ,    1,000,000,0071,000,000,007

입력 샘플
3
aa
aabb
a

출력 샘플
1
2

1

: , , ,ans=0。 , ans=C(n)s[0]*C(n-s[0])s[1].......C(n-s[0]-s[1]...s[i])s[i]; , 。 Cn(i),( mod, ll).

AC:

#include <algorithm> #include <string> #include <iostream> #include <string.h> #include<stdio.h> using namespace std; #define maxn 1100 #define ll __int64 #define mod 1000000007 ll s[365]; ll cn[maxn][maxn]; void cni() {     memset(cn,0,sizeof(cn));     for(int i=0;i<=1000;i++)     {     cn[i][0]=1;     for(int j=1;j<=i;j++)     {         cn[i][j]=(cn[i-1][j-1]+cn[i-1][j])%mod;     }     } } int main() {   char ss[maxn];   ll t,pos,cnt,ans,tp;   cni();   scanf("%I64d",&t);   while(t--)   {       cnt=0;ans=1;       memset(s,0,sizeof(s));       scanf("%s",ss);       for(ll i=0;i<strlen(ss);i++) s[ss[i]]++;       for(int i=0;i<=365;i++)       {           if(s[i]%2==1)           {               cnt++;s[i]--;           }           s[i]=s[i]/2;       }       if(cnt>=2) ans=0;       else       {          ll n; if(cnt==0) n=(strlen(ss))/2; else n=(strlen(ss)-1)/2; tp=n; if(n!=0)          for(int i=0;i<=365;i++)           {                 ans*=(cn[tp][s[i]])%mod;                 ans=ans%mod;                 tp-=s[i];           }       }       printf("%I64d
",ans%mod);   }   return 0; }

좋은 웹페이지 즐겨찾기