問題一覧 > 通常問題

No.1605 Matrix Shape

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 75
作問者 : SPD_9X2SPD_9X2 / テスター : auauaauaua penguinmanpenguinman
13 ProblemId : 6367 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-07-17 00:46:18

問題文

SPD君は、イベント運営の報酬として $N$ 個の行列からなる多重集合 $S$ を貰いました。

$i$ ($1 \le i \le N$) 番目の行列の形状は、 $H_i \times W_i$ です。

沢山の行列は場所を取ってしまうので、SPD君は全ての行列を掛け合わせて $1$ つの行列にしようとしています。

具体的には、 $S$ の要素が $1$ つになる、または掛け合わせることができる $2$ 要素がなくなるまで下の操作を繰り返します。

  • $S$ から $X \cdot Y$ が演算可能な $2$ つの要素 $X$ , $Y$ を選ぶ。 $S$ から $X$ , $Y$ を削除し、$X \cdot Y$ を $S$ に加える。

最後に $S$ の要素が $1$ つになった時、その行列の異なる形状として考えられるものは何通りあるか求めてください。ただし、どのように操作しても $S$ の要素を $1$ つにできない場合は $0$ を出力してください。


$2$つの行列 $X$ ( 形状 $H_X \times W_X$ ) と $Y$ ( 形状 $H_Y \times W_Y$ )に関して、$ X \cdot Y $ は $ W_X = H_Y $ のとき、またその時に限り演算可能であり、その形状は $H_X \times W_Y$ になることに注意してください。

また、 $2$ つの行列の形状が異なるとは、行の数・列の数の内少なくとも片方が異なっていることを指します。

入力

$N$
$H_1\ W_1$
$H_2\ W_2$
$\vdots$
$H_N\ W_N$

  • 入力は全て整数
  • $2 \le N \le 2 \times 10^5$
  • $1 \le H_i \le 2 \times 10^5$
  • $1 \le W_i \le 2 \times 10^5$

出力

最後に改行してください。

サンプル

サンプル1
入力
3
1 2
2 2
2 3
出力
1

サンプル2
入力
2
7 8
8 7
出力
2

掛け合わせる順序によって演算後の行列の形状が変化します。

サンプル3
入力
5
4 2
6 3
5 9
7 1
8 10
出力
0

一度も操作できません。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。