問題一覧 > 通常問題

No.1596 Distance Sum in 2D Plane

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 256
作問者 : e869120e869120 / テスター : hirakich1000000007hirakich1000000007 👑 ygussanyygussany
10 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 円払っての移動はできないことに注意してください。)

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

入力

N M
t1 x1 y1
t2 x2 y2
t3 x3 y3
 
tM xM yM

出力

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

制約

  • 1N200000
  • 0M200000
  • 1ti2
  • ti=1 のとき 0xi<N かつ 0yiN
  • ti=2 のとき 0xiN かつ 0yi<N
  • (t1,x1,y1),(t2,x2,y2),(t3,x3,y3),,(tN,xN,yN) は相異なる
  • 入力はすべて整数

サンプル

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

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

1

サンプル

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

移動方法は 252 通りありますが、すべて「移動にかかる金額」が 10 円であるため、答えは 252×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

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

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