求助站外题

回文（palin）

【题目描述】 给定一个n行m列的只包含小写字母的矩阵A，请求出从(1,1)到(n,m)只向下或向右 走，且路径上的所有字符按照顺序排列可以构成一个回文串的路径条数。 由于答案可能很大，请输出答案在模993244853意义下的结果。

【输入格式】 从文件palin.in 中读入数据。 第一行是两个正整数n,m。 接下来n行，每行是一个长为m的字符串，其中只包含英文小写字母，描述矩阵A的内 容。

【输出格式】 输出到palin.out 中。 输出一行一个非负整数，表示满足条件的路径数模993244853后的值。

【输入样例1】

3 4 noip

ffff

pion

【输出样例1】 2 【样例解释1】 满足条件的路径为(1,1)→(2,1) → (2,2) → (2,3) → (2,4) → (3,4) 和 (1,1) → (1,2) → (2, 2) → (2,3) → (3,3) → (3,4)。

【输入样例2】 4 5

wwwww

wwwww

wwwww

wwwwa

【输出样例2】 0 【样例解释2】 由于左上角和右下角的字符不同，任何路径上的字符都不可能构成回文串。

【数据规模与约定】 对于20%的数据，1≤n,m≤10。

对于35%的数据，1≤n,m≤20。

对于50%的数据，1≤n,m≤80。

对于另外15%的数据，1≤n≤80。

对于另外15%的数据，保证对任意i>1,j<m有Ai,j =Ai−1,j+1。

对于100% 的数据，1≤n,m≤500，输入的矩阵仅包含小写英文字母。