問題一覧 > 通常問題

No.1520 Zigzag Sum

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 63
作問者 : NatsubiSoganNatsubiSogan / テスター : aspiaspi penguinmanpenguinman NachiaNachia
6 ProblemId : 5154 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-05-21 23:44:27

問題文

縦 $H$ マス 横 $W$ マスのグリッドがあります。上から $i$ 行目、左から $j$ 列目のマスを $(i,j)$ と表します。

Natsubi くんがこのグリッド上を $(1,1)$ から $(H,W)$ まで移動します。彼は $(i,j)$ にいるとき、$(i+1,j)$ または $(i,j+1)$ に動く事が出来ます。グリッドの外に移動することはできません。

ある移動経路について、そのジグザグ度を以下のように定義します。

  • 経路上のマスのうち、そこで経路が曲がっているものの数

ここで、あるマス $(i, j)$ で「経路が曲がっている」とは、以下の条件のうちいずれかが成り立っていることを指します。

  • $(i-1,j),\ (i,j),\ (i,j+1)$ がすべて存在し、かつ経路がそれらすべてを通っている。
  • $(i,j-1),\ (i,j),\ (i+1,j)$ がすべて存在し、かつ経路がそれらすべてを通っている。

$H,W$ が与えられるので、$\displaystyle \binom{H+W-2}{H-1}$ 個ある移動経路すべてについてジグザグ度を求め、その総和を答えてください。

ただし、答えは非常に大きくなることがあるので、$10^9+7$ (素数)で割った余りを出力してください。

$T$ 個のテストケースについて答えてください。

入力

入力は標準入力から与えられます。入力の $1$ 行目は以下の通りです。

$T$

そして、続く $T$ 行に $T$ 個のテストケースが与えられます。これらはそれぞれ以下の形式です。

$H\ W$

  • 入力はすべて整数
  • $1 \leq T \leq 10^5$
  • $1 \leq H,W \leq 2 \times 10^5$

出力

各テストケースに対し、答えを出力してください。テストケースごとに改行してください。

サンプル

サンプル1
入力
4
2 3
1 10
1 1
200000 200000
出力
4
0
0
316943316

  • $1$ つ目のケースについて:考えられる移動経路は下図の $3$ 通りです。ジグザグ度はそれぞれ $1,2,1$ なので、$4$ が答えです。
  • $2$ つ目のケースについて:そもそも曲がりようがありません。
  • $3$ つ目のケースについて:もはや移動すらしていませんが、これも答えは $0$ です。
  • $4$ つ目のケースについて:求めた答えを $10^9+7$ で割った余りを出力するのを忘れないでください。

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