管道取珠题解DP

直接入手似乎有些困难，不妨将原问题作一点转化：
输出第i种特定序列的方案数a[i]即为二元组(X, Y)（其中X, Y分别代表一种输出第i种序列的方式，且X与Y相互独立）的组数。
设X所对应的方案为(ix, jx)（从上管道取出了ix个，从下管道取出了jx个），Y所对应的方案为（iy, jy)（含义类似于ix, jx）。
于是，可以用状态f[ix][jx][iy][jy]作一下更新：

1) 若上管道的第(ix + 1)个小球和上管道的第(iy + 1)个小球，那么更新状态f[ix + 1][jx][iy + 1][jy]；
2) 若上管道的第(ix + 1)个小球和下管道的第(jy + 1)个小球，那么更新状态f[ix + 1][jx][iy][jy + 1]；
3) 若下管道的第(jx + 1)个小球和上管道的第(iy + 1)个小球，那么更新状态f[ix][jx + 1][iy + 1][jy]；
4) 若下管道的第(jx + 1)个小球和下管道的第(jy + 1)个小球，那么更新状态f[ix][jx + 1][iy][jy + 1]。
实际上我们知道ix + jx = iy + jy，于是可以减少一维的状态，把jy去掉。
思维性太强了啊 这题

#include <bits/stdc++.h>
using namespace std;
const int maxN = 510, MOD = 1024523;
int f[maxN][maxN][maxN], n, m; char up[maxN], dn[maxN];

inline void Add(int &a, int b)
{if ((a += b) >= MOD) a -= MOD; return;}

int main()
{

    scanf("%d%d%s%s", &n, &m, up + 1, dn + 1); f[0][0][0] = 1;
    for (int ix = 0; ix < n + 1; ++ix)
    for (int jx = 0; jx < m + 1; ++jx)
    for (int iy = 0; iy < n + 1; ++iy)
    if (f[ix][jx][iy])
    {
        int &t = f[ix][jx][iy], jy = ix + jx - iy;
        if (up[ix + 1] == up[iy + 1]) Add(f[ix + 1][jx][iy + 1], t);
        if (up[ix + 1] == dn[jy + 1]) Add(f[ix + 1][jx][iy], t);
        if (dn[jx + 1] == up[iy + 1]) Add(f[ix][jx + 1][iy + 1], t);
        if (dn[jx + 1] == dn[jy + 1]) Add(f[ix][jx + 1][iy], t);
    }
    printf("%d\n", f[n][m][n]);
return 0;
}