题目链接：https://codeforces.com/problemset/problem/570/E
题意：
给出 $n \times m$ 的网格，每一格上有一个小写字母，现在从 $(1,1)$ 位置走到 $(n,m)$ 位置，要求经过路径构成一个回文串。
要求走路方向保证坐标不会减小（即只能往下或者往右走），要求你给出路径方案数目。
题解：
考虑 $f[x_1][y_1][x_2][y_2]$ 表示一端从 $(1,1)$ 出发，走到了 $(x_1,y_1)$，同时另一端从 $(n,m)$ 出发，走到了 $(x_2,y_2)$，此时形成回文串的数目。
这个是不难维护的，主要问题是这个维数过多，开不下。然后不难发现，如果用 $f[step][x_1][x_2]$ 来维护，可以通过步数 $step$ 和 $x$ 算出 $y$，
然后更进一步可以发现 $step$ 不需要全部维护，可以使用滚动优化。
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+;
const int SIZE=; int n,m;
char mp[SIZE][SIZE];
ll f[][SIZE][SIZE]; inline bool In(int x,int y)
{
return <=x && x<=n && <=y && y<=m;
}
int main()
{
cin>>n>>m;
for(int i=;i<=n;i++) scanf("%s",mp[i]+); int now=;
memset(f[now],,sizeof(f[now]));
f[now][][n]=(ll)(mp[][]==mp[n][m]);
for(int step=;step<=(n+m)/-;step++)
{
now^=;
memset(f[now],,sizeof(f[now]));
for(int x1=;x1<=n;x1++)
{
for(int x2=n;x2>=;x2--)
{
int y1=step+-x1, y2=n+m-step-x2;
if(!In(x1,y1) || !In(x2,y2)) continue;
if(mp[x1][y1]!=mp[x2][y2]) continue; f[now][x1][x2]+=f[now^][x1][x2];
f[now][x1][x2]%=mod; f[now][x1][x2]+=f[now^][x1-][x2+];
f[now][x1][x2]%=mod; f[now][x1][x2]+=f[now^][x1-][x2];
f[now][x1][x2]%=mod; f[now][x1][x2]+=f[now^][x1][x2+];
f[now][x1][x2]%=mod;
}
}
} ll ans=;
if((n+m)%)
{
for(int i=;i<=n;i++) ans+=f[now][i][i], ans%=mod;
for(int i=;i<n;i++) ans+=f[now][i][i+], ans%=mod;
}
else
{
for(int i=;i<=n;i++) ans+=f[now][i][i], ans%=mod;
}
cout<<ans<<endl;
}