JXCPC 1006

2019-07-21

这是暴力得到概率然后gcd一下化为最简分数

String

Problem Description

Avin has a string. He would like to uniform-randomly select four characters (selecting the same character is allowed) from it. You are asked to calculate the probability of the four characters being ”avin” in order.

Input

The first line contains $ n (1 \leq n \leq 100) $, the length of the string. The second line contains the string. To simplify the problem, the characters of the string are from ’a’, ’v’, ’i’, ’n’.

Output

Print the reduced fraction (the greatest common divisor of the numerator and denominator is $1$), representing the probability. If the answer is $0$, you should output $”0/1”$.

Sample Input

4
avin
4
aaaa

Sample Output

1/256
0/1

The Code Of My Program

/*********************
*@Author:   ChenShou *
*@Language: C++11    *
*********************/
//#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")
#include<functional>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<sstream>
#include<iomanip> 
#include<numeric>
#include<cctype>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>

//#define DEBUG
#define RI register int
#define endl "\n"

using namespace std;
typedef long long ll;
//typedef __int128 lll;
//const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-9;
const int INF = 0x3f3f3f3f;

inline long long read(){
    long long x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

int main()
{
#ifdef DEBUG
    freopen("input.in", "r", stdin);
    //freopen("output.out", "w", stdout);
#endif
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    //}
    ll m ;
    while(scanf("%lld",&m)!=EOF){
    char s[105];
    scanf("%s",s);
    ll a=0,v=0,i=0,n=0;
    for(ll ii=0;ii<m;ii++){
    	if(s[ii]=='a') a++;
    	if(s[ii]=='v') v++;
    	if(s[ii]=='i') i++;
    	if(s[ii]=='n') n++;
    }
    ll zi = a/__gcd(a,m)*v/__gcd(v,m)*i/__gcd(i,m)*n/__gcd(n,m);
    ll mu = m*m*m*m/__gcd(a,m)/__gcd(v,m)/__gcd(i,m)/__gcd(n,m);
    printf("%lld/%lld\n",zi,mu);

}
#ifdef DEBUG
    printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Fuck You !" << endl;
    return 0;
}