TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P7471
  • 問題
  • P7471[USACO2015 open] Palindromic Paths 回文路径
    制限 : 時間制限 : - MS   メモリ制限 : 524288 KB
    審判説明 : 1s,512MB
    問題説明

    nodgd家的花园是一个 \(N\times N\) 的正方形网格,每个格子里都种了一种花,相同的花用同一个大写英文字母表示。

    花园有两个门,分别在西北角和东南角。nodgd每次都从西北角的门进入花园,每一步都向东或者向南行走,直到从东南角的门离开花园。

    nodgd很喜欢回文,所以nodgd想让你帮忙统计一下,有多少条路径是回文的?答案可能很大, \(\bmod 10^9+7\)

    入力形式

    第一行一个整数 \(N\)

    接下来是一个 \(N\times N\) 的字符矩阵,只包含大写英文字母。

    出力形式

    输出一个整数,表示回文路径的数量。

    サンプル入力

    4
    ABCD
    BXZX
    CDXB
    WCBA

    サンプル出力

    12

    ヒント

    样例说明

    有以下一些回文路径:

    • ABCDCBA 有 $1$ 条
    • ABCWCBA 有 $1$ 条
    • ABXZXBA 有 $6$ 条
    • ABXDXBA 有 $4$ 条

    数据范围

    对于10%的数据, \(N\leq 8\)

    对于45%的数据, \(N\leq 18\)

    对于60%的数据, \(N\leq 150\)

    对于100%的数据, $1\leq N\leq 500$ 。


    ソース  nodgd搬运