C - Team Assignment Lottery Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

高橋君の所属するスポーツクラブには N 人のメンバーがおり、それぞれ 1 から N までの番号が付けられています。メンバー i のランクは S_i で表され、A（初級者）または B（上級者）のいずれかです。高橋君自身はメンバー 1 であり、そのランクは S_1 です。

練習試合のペア決めとして、くじ引きが 1 回行われます。高橋君（メンバー 1）を除いた N - 1 人の中から 1 人が一様ランダムに選ばれ、高橋君のペアの候補となります。すなわち、メンバー 2, 3, \ldots, N のそれぞれが選ばれる確率は等しく \frac{1}{N-1} です。

このペア決めには以下のルールがあります。

  • くじ引きで選ばれた相手のランクが高橋君と同じであった場合、練習の効果が薄いためペアは不成立となります。
  • くじ引きで選ばれた相手のランクが高橋君と異なる場合、ペアは成立します。

高橋君はペアを成立させたいと考えています。このくじ引きでペアが成立する確率を求めてください。

答えを既約分数 \frac{P}{Q}（ただし Q > 0 かつ \gcd(P, Q) = 1）の形で出力してください。確率が 0 の場合は 0/1 と、確率が 1 の場合は 1/1 と出力してください。

制約

  • 2 \leq N \leq 10^6
  • S_i は A または B のいずれかである（1 \leq i \leq N）

入力

N
S_1 S_2 \ldots S_N
  • 1 行目には、クラブのメンバー数を表す整数 N が与えられる。
  • 2 行目には、各メンバーのランクを表す N 個の文字 S_1, S_2, \ldots, S_N がスペース区切りで与えられる。
  • S_i はメンバー i のランクであり、A または B のいずれかである。
  • S_1 は高橋君のランクである。

出力

ペアが成立する確率を既約分数 \frac{P}{Q} の形で、P/Q というフォーマットで 1 行で出力せよ。

入力例 1

4
A A B B

出力例 1

2/3

入力例 2

3
A A A

出力例 2

0/1

入力例 3

10
B A A B A A B A B B

出力例 3

5/9

入力例 4

20
A B B A B A B B A B B A B B B A B A B B

出力例 4

13/19

入力例 5

2
A B

出力例 5

1/1

Score : 300 pts

Problem Statement

There are N members in the sports club that Takahashi belongs to, numbered from 1 to N. The rank of member i is represented by S_i, which is either A (beginner) or B (advanced). Takahashi himself is member 1, and his rank is S_1.

To determine pairs for a practice match, a lottery is held once. From the N - 1 members excluding Takahashi (member 1), one person is chosen uniformly at random as a candidate for Takahashi's pair. That is, each of members 2, 3, \ldots, N is chosen with equal probability \frac{1}{N-1}.

The following rules apply to this pairing:

  • If the rank of the person chosen by the lottery is the same as Takahashi's, the practice would be less effective, so the pair is not formed.
  • If the rank of the person chosen by the lottery is different from Takahashi's, the pair is formed.

Takahashi wants the pair to be formed. Find the probability that a pair is formed in this lottery.

Output the answer as an irreducible fraction \frac{P}{Q} (where Q > 0 and \gcd(P, Q) = 1). If the probability is 0, output 0/1, and if the probability is 1, output 1/1.

Constraints

  • 2 \leq N \leq 10^6
  • S_i is either A or B (1 \leq i \leq N)

Input

N
S_1 S_2 \ldots S_N
  • The first line contains an integer N representing the number of club members.
  • The second line contains N characters S_1, S_2, \ldots, S_N separated by spaces, representing the rank of each member.
  • S_i is the rank of member i, which is either A or B.
  • S_1 is Takahashi's rank.

Output

Output the probability that a pair is formed as an irreducible fraction \frac{P}{Q} in the format P/Q on a single line.

Sample Input 1

4
A A B B

Sample Output 1

2/3

Sample Input 2

3
A A A

Sample Output 2

0/1

Sample Input 3

10
B A A B A A B A B B

Sample Output 3

5/9

Sample Input 4

20
A B B A B A B B A B B A B B B A B A B B

Sample Output 4

13/19

Sample Input 5

2
A B

Sample Output 5

1/1