Description：

有一上一下两个管道，每个管道里有不同数量的深色或浅色珠子，每此可以从两个管道之一的队头取一个珠子，最后会形成一个深浅珠子的序列，设第 $i$ 种最终序列有 $k_i$ 种形成方式，求 $\sum k_i$ 。

$1\leqslant n \leqslant500$

Solution：

直接统计没法统计，因为 $N^2$ 这个东西不能线性相加，不能线性相加就不能简单地合并统计方案，观察一下 $N^2$ 有什么组合含义，可以看成形成两个序列完全相同的方案数，于是有这样一个 $\text{DP}$ ： $f[i][j][k][l]$ 表示第一种方案第一个管道 $i$ 之后的都已经处理了，第二个管道 $j$ 之后都已经被处理了， $k$ 和 $l$ 同理表示第二种方案，发现 $i+j=k+l$ 所以可以省掉一维，转移就是看哪对珠子相同然后累加一下，要用滚动数组。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define MAXN 510

int n,m;

inline char getc()

{

    register char c = getchar();

    while(c != 'A' && c != 'B')c = getchar();

    return c;

}

char a[MAXN],b[MAXN];

int f[2][MAXN][MAXN];

#define MOD 1024523

int main()

{

    scanf("%d%d",&n,&m);

    for(register int i = 1;i <= n;++i)a[i] = getc();

    for(register int i = 1;i <= m;++i)b[i] = getc();

    register int cur = 0;

    f[cur][m][n] = 1;

    for(register int i = n;i >= 0;--i)

    {

        for(register int j = m;j >= 0;--j)

        {

            for(register int k = n;k >= 0;--k)

            {

                register int l = i + j - k;

                if(l > m)break;

                if(l < 0)continue;

                if(a[i + 1] == a[k + 1])f[cur][j][k] = (f[cur][j][k] + f[cur ^ 1][j][k + 1]) % MOD;

                if(b[j + 1] == b[l + 1])f[cur][j][k] = (f[cur][j][k] + f[cur][j + 1][k]) % MOD;

                if(a[i + 1] == b[l + 1])f[cur][j][k] = (f[cur][j][k] + f[cur ^ 1][j][k]) % MOD;

                if(b[j + 1] == a[k + 1])f[cur][j][k] = (f[cur][j][k] + f[cur][j + 1][k + 1]) % MOD;

            }

        }

        cur = cur ^ 1;

        memset(f[cur],0,sizeof(f[cur]));

    }

    cout << f[cur ^ 1][0][0] << endl;

    return 0;

}