51nod 1503 猪和回文（dp滚存）

大意：在一个n*m的矩形中从（1,1）走到（n，m）而且走过的路径是一条回文串，统计方案数

sol：我们考虑从（1,1）和（n，m）两端开始算，这样就只要保证每次经过的字符一样就可以满足回文了，因为一定有一个循环需要枚举步数，知道了步数自然只要知道了x坐标就可以算出y坐标了，于是只要枚举x1和x2了，因为当前这步一定是从上一步转移过来的，就可以滚存了

#include<bits/stdc++.h>

using namespace std;

#define Mod 1000000007

long long n, m, f[][][], ans = ;

char Map[][];

inline void Add(long long &x, long long y){x = (x + y) % Mod;}

int main()

{

    freopen("51nod1503.in","r",stdin);

    while(~scanf("%lld%lld", &n, &m))

    {

        ans = ;

        for(long long i = ; i <= n; i++)

            scanf("%s", Map[i] + );

        if(Map[][] != Map[n][m])

        {

            printf("0\n");

            continue;

        }

        long long cur = ;

        f[cur][][n] = ;

        for(long long step = ; step <= (n + m - ) / ; step++)

        {

            cur ^= ;

            for(long long i = ; i <= n; i++)

            for(long long j = ; j <= n; j++)

                f[cur][i][j] = ;

            for(long long x1 = ; x1 <= n && x1 -  <= step; x1++)

            for(long long x2 = n; x2 >=  && n - x2 <= step; x2--)

            {

                long long y1 =  + (step - (x1 - ));

                long long y2 = m - (step - (n - x2));

                if (Map[x1][y1] != Map[x2][y2]) continue;

                Add(f[cur][x1][x2], f[cur ^ ][x1 - ][x2 + ]);

                Add(f[cur][x1][x2], f[cur ^ ][x1 - ][x2]);

                Add(f[cur][x1][x2], f[cur ^ ][x1][x2 + ]);

                Add(f[cur][x1][x2], f[cur ^ ][x1][x2]);

            }

        }

        for(long long i = ; i <= n; i++)

            Add(ans, f[cur][i][i]);

        if((n + m) & )

        for(long long i = ; i < n; i++)

            Add(ans, f[cur][i][i + ]);

        printf("%lld\n", ans);

    }

}