어떤 나라들은 대통령을 단순히 전체 득표수로만 뽑지 않는다. 예를 들어 현실의 어떤 선거 제도에서는 유권자가 대통령을 직접 뽑는 것처럼 보이지만, 실제로는 각 주에 배정된 선거인들이 대통령을 뽑는 간접 선거 구조를 사용한다.

각 주에는 일정 수의 선거인이 배정되어 있고, 대부분의 주에서는 그 주에서 가장 많은 표를 얻은 후보가 그 주의 선거인을 모두 가져간다. 이런 방식을 흔히 승자독식이라고 부른다.

하지만 모든 주가 똑같이 행동하는 것은 아니다. 어떤 주는 주 전체 결과뿐 아니라 선거구별 결과에 따라 선거인을 나누어 배정하기도 한다. 즉, 한 후보가 어떤 선거구에서는 이기고, 다른 후보가 다른 선거구에서는 이길 수 있다. 그러면 한 주의 선거인단 표가 여러 후보에게 나뉘어 갈 수 있다.

또한 아주 드물게, 어떤 선거인은 자신이 배정된 후보가 아닌 다른 후보에게 실제 투표를 할 수도 있다. 이런 선거인을 흔히 배신 선거인이라고 부른다.

알파카 공화국은 이런 복잡한 제도를 더욱 알파카답게 바꿔서 사용한다. 이 문제에서는 알파카 공화국의 선거 결과를 확률적으로 계산해야 한다.

알파카 공화국에는 대통령을 선출하기 위한 복잡한 선거 제도가 존재한다.

이번 선거에는 총 \(C\)명의 후보가 출마한다. 각 후보는 서로 다른 이름을 가진다. 알파카 공화국은 \(S\)개의 주로 이루어져 있으며, 각 주는 다음 두 종류 중 하나이다.

첫 번째 종류는 승자독식 주이다. 이 주에는 \(E\)명의 선거인과 \(V\)명의 유권자가 있다. 각 유권자는 서로 독립적으로 투표하며, 한 유권자가 후보 \(j\)에게 투표할 확률은 \(p_j\)이다.

투표가 끝난 뒤 가장 많은 표를 얻은 후보가 이 주의 선거인 \(E\)명을 모두 배정받는다. 만약 가장 많은 표를 얻은 후보가 여러 명이라면, 그 후보들 중 한 명이 같은 확률로 선택되어 선거인 \(E\)명을 모두 배정받는다.

두 번째 종류는 선거구 주이다. 이 주에는 \(D\)개의 선거구와 \(B\)명의 주 전체 보너스 선거인이 있다. \(i\)번째 선거구에는 \(E_i\)명의 선거인과 \(V_i\)명의 유권자가 있다. \(i\)번째 선거구의 각 유권자는 서로 독립적으로 투표하며, 한 유권자가 후보 \(j\)에게 투표할 확률은 \(p_{i,j}\)이다.

각 선거구에서는 그 선거구에서 가장 많은 표를 얻은 후보가 해당 선거구의 선거인 \(E_i\)명을 모두 배정받는다. 만약 가장 많은 표를 얻은 후보가 여러 명이라면, 그 후보들 중 한 명이 같은 확률로 선택되어 해당 선거구의 선거인 \(E_i\)명을 모두 배정받는다.

또한 선거구 주에서는 모든 선거구의 투표 결과를 합산하여 주 전체 득표수를 계산한다. 주 전체에서 가장 많은 표를 얻은 후보는 보너스 선거인 \(B\)명을 모두 배정받는다. 만약 주 전체에서 가장 많은 표를 얻은 후보가 여러 명이라면, 그 후보들 중 한 명이 같은 확률로 선택되어 보너스 선거인 \(B\)명을 모두 배정받는다.

모든 주에서 선거인이 배정된 뒤, 각 선거인은 실제 투표를 한다. 이때 선거인은 자신이 배정된 후보에게 반드시 투표하지 않을 수도 있다. 후보 \(a\)에게 배정된 선거인이 실제로 후보 \(b\)에게 투표할 확률은 \(q_{a,b}\)이다. 각 선거인의 실제 투표는 서로 독립이다.

모든 선거인의 실제 투표가 끝난 뒤, 가장 많은 선거인단 표를 얻은 후보가 대통령으로 당선된다. 만약 가장 많은 선거인단 표를 얻은 후보가 여러 명이라면, 그 후보들 중 한 명이 같은 확률로 선택되어 대통령으로 당선된다.

각 후보가 대통령으로 당선될 확률을 구하라. 모든 확률은 \(998244353\)으로 나눈 나머지로 출력해야 한다.

입력으로 주어지는 모든 확률은 기약분수일 필요는 없는 분수 \(\frac{x}{y}\)의 형태로 주어진다. 이는 모듈러 \(998244353\)에서

$$ x \cdot y^{-1} \pmod{998244353} $$

로 해석한다. 여기서 \(y^{-1}\)은 \(y\)의 \(998244353\)에 대한 곱셈 역원이다.

• $$ 2 \le C \le 3 $$

• $$ 1 \le S \le 51 $$

• 모든 주와 선거구를 합친 전체 선거인의 수를 \(E_{\text{tot}}\)라 하자.

• $$ 1 \le E_{\text{tot}} \le 300 $$

• 모든 선거구 주의 선거구 개수의 합을 \(D_{\text{tot}}\)라 하자.

$$ 0 \le D_{\text{tot}} \le 80 $$

• 승자독식 주에서,

$$ 1 \le E \le 20 $$

$$ 1 \le V \le 50 $$

• 선거구 주에서,

$$ 1 \le D \le 20 $$

$$ 0 \le B \le 20 $$

• 각 선거구 \(i\)에 대해,

$$ 1 \le E_i \le 20 $$

$$ 1 \le V_i \le 50 $$

• 모든 후보 이름, 주 이름, 선거구 이름은 알파벳 대문자와 소문자로만 이루어진 길이 \(1\) 이상 \(20\) 이하의 문자열이다.

• 후보 이름은 서로 다르다. 주 이름은 서로 다르다. 같은 주 안에서 선거구 이름은 서로 다르다.

• 후보 이름, 주 이름, 선거구 이름이 서로 같은 문자열일 수도 있다. 단, 문맥에 따라 구분된다.

• 모든 확률은 \(x/y\) 형태로 주어지며 \(0 \le x \le y\), \(1 \le y < 998244353\)이다.

• 각 확률 분포의 합은 항상 \(1\)이다. 즉, 모든 후보 \(a\)에 대해 \(\sum_{b=1}^{C} q_{a,b} = 1\)이고, 모든 승자독식 주에 대해 \(\sum_{j=1}^{C} p_j = 1\)이며, 모든 선거구 \(i\)에 대해 \(\sum_{j=1}^{C} p_{i,j} = 1\)이다.

첫째 줄에 후보의 수 \(C\)와 주의 수 \(S\)가 공백으로 구분되어 주어진다.

둘째 줄에는 \(C\)개의 서로 다른 후보 이름이 공백으로 구분되어 주어진다.

다음 \(C^2\)개의 줄에는 배신 선거인 확률이 주어진다. 각 줄은 다음 형태이다.

$$ A \quad B \quad x/y $$

이는 후보 \(A\)에게 배정된 선거인이 실제로 후보 \(B\)에게 투표할 확률이 \(\frac{x}{y}\)임을 의미한다.

이후 \(S\)개의 주에 대한 정보가 차례대로 주어진다.

각 주의 첫 번째 줄에는 주 이름 \(Z\)와 주의 종류 \(T\)가 공백으로 구분되어 주어진다.

$$ T \in \{1,2\} $$

만약 \(T=1\)이라면, 이 주는 승자독식 주이다. 다음 줄에 선거인의 수 \(E\)와 유권자의 수 \(V\)가 공백으로 구분되어 주어진다.

그 다음 \(C\)개의 줄에는 각 후보의 득표 확률이 다음 형태로 주어진다.

$$ A \quad x/y $$

이는 이 주의 한 유권자가 후보 \(A\)에게 투표할 확률이 \(\frac{x}{y}\)임을 의미한다.

만약 \(T=2\)라면, 이 주는 선거구 주이다. 다음 줄에 선거구의 수 \(D\)와 주 전체 보너스 선거인의 수 \(B\)가 공백으로 구분되어 주어진다.

이후 각 선거구에 대해 다음 정보가 주어진다.

먼저 선거구 이름 \(Y\)가 주어진다.

다음 줄에 선거인의 수 \(E_i\)와 유권자의 수 \(V_i\)가 공백으로 구분되어 주어진다.

그 다음 \(C\)개의 줄에는 각 후보의 득표 확률이 다음 형태로 주어진다.

$$ A \quad x/y $$

이는 해당 선거구의 한 유권자가 후보 \(A\)에게 투표할 확률이 \(\frac{x}{y}\)임을 의미한다.

첫째 줄에 \(C\)개의 정수 \(ans_1, ans_2, \ldots, ans_C\)를 공백으로 구분하여 출력한다.

\(ans_i\)는 입력에서 \(i\)번째로 주어진 후보가 대통령으로 당선될 확률을 \(998244353\)으로 나눈 나머지이다.

즉, 실제 확률이 기약분수 \(\frac{x}{y}\)라면,

$$ ans_i \equiv x \cdot y^{-1} \pmod{998244353} $$

를 만족해야 한다.

rip 작성

출처 알파카컵 2회