关于回文路径(金组) 的近10条评论(全部评论)
回复 @葳棠殇 : CF某题跟这个一样吗？ Satoshi 2016-04-05 07:56 3楼
回复 @葳棠殇 : 好(diao)的样子，跪跪跪 000 2016-04-04 21:24 2楼
做完CF，直接就交了，没看清样例，WA了一发，QAQ 葳棠殇 2016-04-04 21:09 1楼

2208. [USACO US open15]回文路径(金组)

★★★☆ 输入文件：palpath.in 输出文件：palpath.out 简单对比
时间限制：1 s 内存限制：256 MiB

FJ的农场是一个$NxN$的网格，每个网格用字母标记，比如：

$ABCD$

$BXZX$

$CDXB$

$WCBA$

每天，奶牛$Bessie$从左上角走到右下角，每步要么往右走一格，要么往下走一格，

$Bessie$保存她在这个过程中走过的字母形成的路径字符串.她感到迷失了方向.然而，如果这个字符串是一个回文串(从前读和从后读一样)，她就会为到底走的是哪一个方向而感到困惑。

请帮助$Bessie$找出不同回文字符串路径的总数。不同路径所组成的相同回文字符串将会被统计多次。请输出结果$\mod{1,000,000,007}$的值

第一行一个正整数$N$

接下来$N$行每行$N$个字符

只有一个整数，为所有包含不同路径的回文字符串的数目$\mod{1,000,000,007}$的值

ABCD

BXZX

CDXB

WCBA

$Bessie$可以产生以下回文串:

1 个 $"ABCDCBA"$

1 个 $"ABCWCBA"$

6 个 $"ABXZXBA"$

4 个 $"ABXDXBA"$

总共12个

数据范围:

对于16.67%的数据,$N<=23$

对于41.67%的数据,$N<=280$

对于100%的数据,$N<=500$

译者注：请注意常数因子对于程序的影响

USACO 2015 US open Gold