No.2572 Midori on the grid
レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 20
作問者 :
ragna
/ テスター :
deuteridayo
👑
AngrySadEight
kusirakusira
Magentor
aplysiaSheep
けんぴん
タグ : / 解いたユーザー数 20
作問者 :
![ragna](https://pbs.twimg.com/profile_images/1656489814416568320/xcQX_4Ni.jpg)
![AngrySadEight](https://pbs.twimg.com/profile_images/1774819988135927808/f4w6hc33.jpg)
![kusirakusira](https://pbs.twimg.com/profile_images/1708448431939940352/dT9ikwU_.jpg)
![Magentor](https://pbs.twimg.com/profile_images/1715389554197495808/7HlNzj_p.jpg)
![aplysiaSheep](https://pbs.twimg.com/profile_images/1755875215937265664/DA7ZDzYk.jpg)
![けんぴん](https://pbs.twimg.com/profile_images/1450188204762550276/vcIHgyD4.jpg)
問題文最終更新日: 2023-12-01 12:58:32
問題文
平面上に格子点 があり、隣り合う格子点同士は辺でつながれています。
みどりさんは点 にいて、辺に沿って移動して最短距離で点 に行きたいです。
個の整数 が与えられるので、みどりさんが通る経路の選び方のうち、各直線 上の点を通らない経路の選び方を求めてください。
ただし、答えは非常に大きくなる可能性があるため で割った余りを出力してください。
格子点が隣り合っているとは
格子点 と が隣り合っているとは かつ が成り立つことを指します。
例えば、 と隣り合っている格子点は のつです。
制約
- 直線 は点 も点 も通らない
- 入力はすべて整数である
入力
出力
行出力してください。 行目 には に対する答えを出力してください。
サンプル
サンプル1
入力
2 1 1 1
出力
2
点 が通れないため、
- → → →
- → → →
サンプル2
入力
200 100 5 24 129 -35 63 100
出力
481605547 514334971 0 19509670 514334970
で割った余りを出力することに気を付けてください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。