记录编号	578193	评测结果	AAAAAAAAA
题目名称	[NOI 2009]管道取珠	最终得分	100
用户昵称	zxhhh	是否通过	通过
代码语言	C++	运行时间	1.770 s
提交时间	2023-02-15 20:24:58	内存使用	6.87 MiB

#include <bits/stdc++.h>

using namespace std;

const int N = 505, mod = 1024523;
typedef long long ll; 

int n, m;
char a[N], b[N];
ll dp[5][N][N];

int main () {
	freopen("ballb.in", "r", stdin);
	freopen("ballb.out", "w", stdout);
	cin >> n >> m;
	scanf("%s %s", a + 1, b + 1);
	reverse(a + 1, a + 1 + n); reverse(b + 1, b + 1 + m);
	dp[0][0][0] = 1; int idx = 0;
	for (int i = 0;i <= n;i++, idx ^= 1) {
		for (int j = 0;j <= m;j++) {
			for (int z = 0;z <= n && z <= i + j;z++) {
				int q = i + j - z;
				if (!i && !j && !z) continue;
				ll t = 0;
				if (q > m) continue;
				if (a[i] == a[z] && (i && z > 0)) t += dp[idx ^ 1][j][z - 1];
				if (a[i] == b[q] && (i && q > 0)) t += dp[idx ^ 1][j][z];
				if (b[j] == a[z] && (j > 0 && z > 0)) t += dp[idx][j - 1][z - 1];
				if (b[j] == b[q] && (j > 0 && q > 0)) t += dp[idx][j - 1][z];
				dp[idx][j][z] = t % mod;
			}
		}
	}
	printf("%lld\n", dp[idx ^ 1][m][n]);
	return 0;
}