No.1916 Making Palindrome on Gird
レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 82
作問者 :
とりゐ
/ テスター :
箱星
riano
タグ : / 解いたユーザー数 82
作問者 :
とりゐ
/ テスター :
箱星
riano
問題文最終更新日: 2022-04-25 23:33:42
問題文
$H$ 行 $W$ 列のグリッドがあり，上から $i$ 行目，左から $j$ 列目のマス $(i,j)$ には文字 $S_{ij}$ が書かれています．
以下の操作で長さ $H+W-1$ の文字列を作ることを考えます．
- 最初に空の文字列 $T$ を用意してマス $(1,1)$ に立つ．
-
その後，以下のルールで移動する．
- マス $(H,W)$ にいるとき，文字列 $T$ の末尾に文字 $S_{HW}$ を追加して操作を終了する．
-
そうでなければ，マス $(i,j)$ にいるとき文字列 $T$ の末尾に文字 $S_{ij}$ を追加する．その後，マス $(i+1,j)$ または $(i,j+1)$ に移動する．
- ただし，$i=H$ のとき $(i+1,j)$ への移動は許されない．
- さらに，$j=W$ のとき $(i,j+1)$ への移動は許されない．
マス $(1,1)$ から $(H,W)$ に移動する方法は ${}_{H+W-2}\mathrm{C}_{H-1}$ 通りありますが，このうち得られる文字列が回文になるような移動方法は何通りありますか．$10^9+7$ で割った余りを求めてください．
入力
$H$ $W$
$S_{11}\ \ldots\ S_{1W}$
$\vdots$
$S_{H1}\ \ldots\ S_{HW}$
- $1\leq H,W\leq 200$
- $H,W$ は整数である
- $S_{ij}$ は英小文字である
出力
得られる文字列が回文となるような移動方法の総数を $10^9+7$ で割った余りを出力してください．
サンプル
サンプル1
入力
3 3 abc cbc dca
出力
3
以下の $6$ 通りの移動方法があります．
- $(1,1)\to(1,2)\to(1,3)\to(2,3)\to(3,3)$ と移動するとき，文字列
abccaが得られる． - $(1,1)\to(1,2)\to(2,2)\to(2,3)\to(3,3)$ と移動するとき，文字列
abbcaが得られる． - $(1,1)\to(1,2)\to(2,2)\to(3,2)\to(3,3)$ と移動するとき，文字列
abbcaが得られる． - $(1,1)\to(2,1)\to(2,2)\to(2,3)\to(3,3)$ と移動するとき，文字列
acbcaが得られる． - $(1,1)\to(2,1)\to(2,2)\to(3,2)\to(3,3)$ と移動するとき，文字列
acbcaが得られる． - $(1,1)\to(2,1)\to(3,1)\to(3,2)\to(3,3)$ と移動するとき，文字列
acdcaが得られる．
サンプル2
入力
4 4 abcd efgh ijkl mnop
出力
0
得られる文字列はすべて回文ではありません．
サンプル3
入力
20 20 aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa
出力
345263555
$10^9+7$ で割った余りを出力してください．
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。