求める確率が \(p/q\) であるとすると、

• \(p = \) (\(i=2,3,\dots,N\) のうち、 \(S_1 \neq S_i\) であるものの個数)
• \(q = N-1\)

となります。これは容易に求めることができます。

しかし、本問題では答えとして 既約分数 を出力する必要があります。つまり、約分をする必要があります。

約分のやり方として、 \(g=\gcd(p,q)\) ( \(\gcd\) は最大公約数) として、 \(p,q\) をともに \(g\) で割るという方法があります。こうすることで、分母分子をともに割り切る \(2\) 以上の整数が存在しなくなり、約分が完了します。
一部の言語では \(\gcd\) が標準で実装されているので、利用するとよいでしょう。

この解法は \(0/1\) あるいは \(1/1\) でもうまく動作します。

本解法の時間計算量は \(O(N)\) です。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int N;
  cin >> N;
  vector<string> S(N);
  cin >> S[0];
  int p=0,q=(N-1);
  for(int i=1;i<N;i++){
    cin >> S[i];
    if(S[0]!=S[i]){p++;}
  }
  int g=gcd(p,q);
  cout << p/g << "/" << q/g << "\n";
  return 0;
}