ZCC loves strings

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/131072 K (Java/Others)
Total Submission(s): 184 Accepted Submission(s): 70

Problem Description ZCC has got N strings. He is now playing a game with Miss G.. ZCC will pick up two strings among those N strings randomly(A string can't be chosen twice). Each string has the same probability to be chosen. Then ZCC and Miss G. play in turns. Miss G. always plays first. In each turn, the player can choose operation A or B.

Operation A: choose a non-empty string between two strings, and delete a single letter at the end of the string.

Operation B: When two strings are the same and not empty, empty both two strings.

The player who can't choose a valid operation loses the game.

ZCC wants to know what the probability of losing the game(i.e. Miss G. wins the game) is.
Input The first line contains an integer $T(T\leq 5)$ which denotes the number of test cases.

For each test case, there is an integer $N(2 \leq N\leq 20000)$ in the first line. In the next N lines, there is a single string which only contains lowercase letters. It's guaranteed that the total length of strings will not exceed 200000.
Output For each test case, output an irreducible fraction "p/q" which is the answer. If the answer equals to 1, output "1/1" while output "0/1" when the answer is 0.
Sample Input

1
3
xllendone
xllendthree
xllendfour

Sample Output

2/3

Source BestCoder Round #41

/* ***********************************************
Author        :CKboss
Created Time  :2015年05月16日 星期六 23时21分46秒
File Name     :B2.cpp
************************************************ */

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include
             using namespace std; map
             
               msi; vector
              
                vs; string str; int n; typedef long long int LL; int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int T_T; scanf("%d",&T_T); while(T_T--) { scanf("%d",&n); vs.clear(); msi.clear(); LL ji=0,ou=0; for(int i=0;i
               
                >str; vs.push_back(str); msi[str]++; if(str.length()%2==0) ou++; else ji++; } LL p=ji*ou; LL q=(LL)n*(n-1)/2; for(int i=0;i
                
                 1) { p+=num*(num-1)/2; msi[vs[i]]=0; } } if(p==0) puts("0/1"); else { int g=__gcd(p,q); printf("%I64d/%I64d\n",p/g,q/g); } } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：poj 2955 Brackets(区间DP求最长..	下一篇：CodeForces-Learning Languages

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: