记录编号	616527	评测结果	AAAAAAAAA
题目名称	[NOI 2009]管道取珠	最终得分	100
用户昵称	RpUtl	是否通过	通过
代码语言	C++	运行时间	0.418 s
提交时间	2026-06-26 19:05:09	内存使用	4.34 MiB

#include <bits/stdc++.h>
using namespace std;
const int N = 505;
const int mod = 1024523;
int n, m, f[2][N][N], ans;
char s[N], t[N];
void Add(int &x, int y) {
	x += y;
	if (x >= mod) x -= mod;
	return;
}
int main(){
	freopen("ballb.in", "r", stdin);
	freopen("ballb.out", "w", stdout);
	scanf("%d %d", &n, &m);
	scanf("%s", s + 1);
	scanf("%s", t + 1);
	f[0][0][0] = 1;
	for (int i = 0; i < n + m; i++) {
		int o = (i & 1);
		for (int j = 0; j <= n; j++) {
			for (int k = 0; k <= n; k++) {
				if (!f[o][j][k]) continue;
				if (j < n && k < n && s[j + 1] == s[k + 1]) {
					Add(f[o ^ 1][j + 1][k + 1], f[o][j][k]) ;
				}	
				if (j < n && i - k < m && s[j + 1] == t[i - k + 1]) {
					Add(f[o ^ 1][j + 1][k], f[o][j][k]);
				}
				if (i - j < m && k < n && t[i - j + 1] == s[k + 1]) {
					Add(f[o ^ 1][j][k + 1], f[o][j][k]);
				}
				if (i - j < m && i - k < m && t[i - j + 1] == t[i - k + 1]) {
					Add(f[o ^ 1][j][k], f[o][j][k]);
				}
				f[o][j][k] = 0;
			}
		}
	}
	int o = (n + m) & 1;
	for (int j = 0; j <= n; j++) {
		for (int k = 0; k <= n; k++) {
			(ans += f[o][j][k]) %= mod;
		}
	}
	printf("%d\n", ans);
	return 0;
}