HDU 6572 String

String

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)

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 ≤ n ≤ 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

思路：

实际上就是求总概率就是avin的分概率相乘，所以下端就是n * n * n * 上面就是4字母个数量相乘，这样得出来的就是概率总和值了。

#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
using namespace std;
int gcd(int a, int b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}
int main() {
    ios::sync_with_stdio;
    int n;
    string s;
    while (scanf("%d", &n) != EOF) {
        int a[256] = {0};
        cin >> s;
        for (int i = 0; i < s.size(); i++) a[s[i]]++;
        int y = n * n * n * n;
        int x = a['v'] * a['a'] * a['i'] * a['n'];
        if (x == 0) printf("0/1\n");
        else {
            int gc = gcd(x, y);
            x /= gc;
            y /= gc;
            printf("%d/%d\n", x, y);
        }
    }
    return 0;
}