問題一覧 > 通常問題

No.1999 Lattice Teleportation

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 24
作問者 : MasKoaTSMasKoaTS / テスター : colognecologne potato167potato167
2 ProblemId : 7721 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-07-01 22:51:13

お詫び(2022/07/01 22:50頃)

サンプル1の説明文1行目に誤りがありました。
「魔法3使用後」となっている箇所は、正しくは「魔法2使用後」です。当該箇所を訂正しました。

皆様にご迷惑をおかけし、大変申し訳ありません。

問題文

魔法使いのコアさんは、二次元平面上で $1, 2, \dots, N$ の番号が付いた $N$ 個の転移魔法を使用できます。

コアさんが座標 $(x, y)$ の点にいるときに転移魔法 $i$ $(1 \leq i \leq N)$ を使用すると、
座標 $(x, y)$, $( x + A_{i}, y + B_{i} )$ の $2$ 点を結ぶ線分(端点を含む)上の好きな点に転移できます。
ただし、$(A_{i}, B_{i} ) = (0, 0)$ の場合、コアさんの位置は座標 $(x, y)$ のまま変化しません。

コアさんは、最初座標 $(0, 0)$ の点に立っており、これから先の転移魔法 $1, 2, \dots, N$ を
この順にすべて $1$ 回ずつ使用します。

このとき、コアさんが転移魔法 $N$ を使用した後に到達し得る格子点の座標は何種類ありますか?
答えは非常に大きくなる可能性があるので、$10^{9} + 7$ で割った余りを出力してください。

なお、「格子点」とは、二次元平面上で $x$ 座標と $y$ 座標がともに整数である点を指します。

制約

  • $1 \leq N \leq 10^{5}$

  • $-10^{9} \leq A_{i}, B_{i} \leq 10^{9}$ $(1 \leq i \leq N)$

  • 入力はすべて整数

入力

入力は次の形式で与えられます。

$N$
$A_{1}$ $B_{1}$
$A_{2}$ $B_{2}$
   $\vdots$
$A_{N}$ $B_{N}$
  • $1$ 行目には $N$ が与えられる

  • $(1 + i)$ $(1 \leq i \leq N)$ 行目には $A_{i}$ と $B_{i}$ がこの順に半角スペース区切りで与えられる

出力

答えを $1$ 行に出力し、最後に改行してください。

サンプル

サンプル1
入力
2
2 0
1 2
出力
8

コアさんが魔法 $2$ 使用後に到達し得る格子点の座標は

  $(0, 0)$, $(1, 0)$, $(2, 0)$, $(1, 1)$, $(2, 1)$, $(1, 2)$, $(2, 2)$, $(3, 2)$

の $8$ 種類です。

例えば座標 $(2, 1)$ の点に到達したい場合、

  1. 魔法 $1$ を使って座標 $\displaystyle \left( \frac{ 3 }{ 2 }, 0 \right)$ の点に移動

  2. 魔法 $2$ を使って座標 $( 2, 1 )$ の点に移動

とすれば良いです。

サンプル2
入力
1
6 -8
出力
3

条件を満たす点の座標は

  $(0, 0)$, $(3, -4)$, $(6, -8)$

の $3$ 種類です。

サンプル3
入力
4
0 0
0 0
0 0
0 0
出力
1

条件を満たす点の座標は $(0, 0)$ のみです。

サンプル4
入力
10
521309021 308664469
-582348421 970764886
-963023827 -504503609
-819305054 316985726
48397449 237116403
-268699958 546643299
656066464 740195508
365802487 -484426411
-684041610 -988265057
-247873784 142659349
出力
520304203

答えを $10^{9} + 7$ で割った余りを求めてください。

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