問題一覧 > 通常問題

No.1596 Distance Sum in 2D Plane

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 223
作問者 : e869120e869120 / テスター : hirakich1000000007hirakich1000000007 👑 ygussanyygussany
9 ProblemId : 6419 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-07-08 23:25:39

問題文

$2$ 次元平面があり、あなたは今いる座標 $(0, 0)$ から目的地の座標 $(N, N)$ に移動したいです。
あなたがマス $(r, c)$ にいるとき、あなたは次の $2$ 種類の移動を行うことができます。

  • 基本的に $1$ 円払い、マス $(r, c)$ からマス $(r+1, c)$ へ移動する。この移動は $r < N$ のとき使える。
  • 基本的に $1$ 円払い、マス $(r, c)$ からマス $(r, c+1)$ へ移動する。この移動は $c < N$ のとき使える。

しかし、次の $M$ 個の移動だけは無料で行うことができます。(逆に、$1$ 円払っての移動はできないことに注意してください。)

  • $t_i = 1$ のとき:マス $(x_i, y_i)$ からマス $(x_i + 1, y_i)$ への移動が無料で行える。
  • $t_i = 2$ のとき:マス $(x_i, y_i)$ からマス $(x_i, y_i + 1)$ への移動が無料で行える。
移動方法は何通りも考えられますが、そのすべてに対して「移動にかかる金額」を合計した値を $10^9+7$ で割った余りはいくつでしょうか。

入力

$N$ $M$
$t_1$ $x_1$ $y_1$
$t_2$ $x_2$ $y_2$
$t_3$ $x_3$ $y_3$
 $\vdots$
$t_M$ $x_M$ $y_M$

出力

答えを出力してください。

制約

  • $1 \leq N \leq 200000$
  • $0 \leq M \leq 200000$
  • $1 \leq t_i \leq 2$
  • $t_i = 1$ のとき $0 \leq x_i < N$ かつ $0 \leq y_i \leq N$
  • $t_i = 2$ のとき $0 \leq x_i \leq N$ かつ $0 \leq y_i < N$
  • $(t_1, x_1, y_1), (t_2, x_2, y_2), (t_3, x_3, y_3), \dots, (t_N, x_N, y_N)$ は相異なる
  • 入力はすべて整数

サンプル

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

下図の通り、移動方法は $6$ つあります。金額の総和は $3 + 3 + 3 + 4 + 4 + 4 = 21$ 円です。

1

サンプル

サンプル2
入力
5 0
出力
2520

移動方法は $252$ 通りありますが、すべて「移動にかかる金額」が $10$ 円であるため、答えは $252 \times 10 = 2520$ です。

サンプル3
入力
400 10
2 73 190
2 351 261
1 164 365
1 62 221
1 18 209
1 358 211
2 32 206
1 147 46
1 36 77
2 5 203
出力
85571926

「移動にかかる金額」を $10^9+7$ で割った余りを出力してください。

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