問題一覧 > 通常問題

No.2003 Frog on Grid

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 21
作問者 : to-omerto-omer / テスター : hamamuhamamu 👑 ygussanyygussany
1 ProblemId : 7716 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-07-05 22:14:19

問題文

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

カエルの現在位置のマスを $(x,y)$ としたとき、1回のジャンプで以下の条件をすべて満たすグリッド内のマス $(x+a,y+b)$ のうちいずれかに移動することができます。

  • $a, b$ は非負整数
  • $1\le a+b\le K$

ただし、いくつかのマスは穴になっていて、そのマスには移動することが出来ません。$c_{i,j}$ が # のときマス $(i,j)$ が穴であることを、 . のときそうでないことを表します。マス $(1,1)$ およびマス $(H,W)$ は穴でないことが保証されています。

カエルが $(1,1)$ から $(H,W)$ まで移動することができる経路の数を求めてください。ただし、答えは非常に大きくなることがあるので、 $998244353$ で割った余りを求めてください。

制約

  • $H,W,K$ は正整数である。
  • $2\le \textcolor{red}{HW}\le 10^6$
  • $1\le K \le H+W-2$
  • $c_{i,j}$ は .# である。
  • $c_{1,1}$ および $c_{H,W}$ は . である。

入力

$H$ $W$ $K$
$c_{1,1}c_{1,2}\dots c_{1,W}$
$c_{2,1}c_{2,2}\dots c_{2,W}$
$\vdots$
$c_{H,1}c_{H,2}\dots c_{H,W}$

出力

カエルが $(1,1)$ から $(H,W)$ まで移動することができる経路の数を $998244353$ で割った余りを 1 行で出力してください。

サンプル

サンプル1
入力
3 3 2
...
##.
.#.
出力
6

以下の 6 通りの経路があります。

  • $(1,1)\to(1,2)\to(1,3)\to(2,3)\to(3,3)$
  • $(1,1)\to(1,2)\to(1,3)\to(3,3)$
  • $(1,1)\to(1,2)\to(2,3)\to(3,3)$
  • $(1,1)\to(1,3)\to(2,3)\to(3,3)$
  • $(1,1)\to(1,3)\to(3,3)$
  • $(1,1)\to(3,1)\to(3,3)$
サンプル2
入力
5 4 3
...#
.###
#...
###.
.#..
出力
53
サンプル3
入力
4 7 9
.......
.......
.......
.......
出力
6080

$998244353$ で割った余りを求めてください。

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