問題一覧 > 通常問題

No.1916 Making Palindrome on Gird

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 72
作問者 : とりゐとりゐ / テスター : koboshikoboshi rianoriano
6 ProblemId : 7805 / 出題時の順位表 / 自分の提出
問題文最終更新日: 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 が得られる.
回文が得られる移動方法は $3$ つです.

サンプル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もしくは右上の雲マークをクリックしてアカウントを作成してください。