题目
输入格式
第一行包含两个整数n, m，分别表示上下两个管道中球的数目。 第二行为一个AB字符串，长度为n，表示上管道中从左到右球的类型。其中A表示浅色球，B表示深色球。 第三行为一个AB字符串，长度为m，表示下管道中的情形。
输出格式
仅包含一行，即为 Sigma(Ai^2) i从1到k 除以1024523的余数。
输入样例
2 1
AB
B
输出样例
5
提示
样例即为文中(图3)。共有两种不同的输出序列形式，序列BAB有1种产生方式，而序列BBA有2种产生方式，因此答案为5。
【大致数据规模】
约30%的数据满足 n, m ≤ 12；
约100%的数据满足n, m ≤ 500。
题解
一开始看题很是懵B
各种相同取法数量的平方之和= =
可以这样想，假如有两人各玩一次，其中一种取法个数为x，第一个人会从x种取法种选一种取，第二个人也从x个取法中选一个取，总共方案不就是(x^2)？
问题不就转化成了：两个人取球，取得相同结果的方案数
设(f[i][j][k])表示取i个球，①号取了上边j个，②号取了上边k个，结果相同的方案数
转移就很简单了，看代码吧
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define BUG(s,n) for (int i = 1; i <= (n); i++) cout<<s[i]<<' '; puts("");
using namespace std;
const int maxn = 505,maxm = 100005,INF = 1000000000,P = 1024523;
int f[2][maxn][maxn],n,m,N;
char L[maxn],R[maxn];
int main(){
scanf("%d%d%s%s",&n,&m,L + 1,R + 1); N = n + m;
for (int i = 1; i <= (n >> 1); i++) swap(L[i],L[n - i + 1]);
for (int i = 1; i <= (m >> 1); i++) swap(R[i],R[m - i + 1]);
f[0][0][0] = 1; int p = 0;
for (int i = 0; i < N; i++,p ^= 1)
for (int j = 0; j <= n && j <= i; j++)
for (int k = 0; k <= n && k <= i; k++){
int F = f[p][j][k];
if (L[j + 1] == L[k + 1])
f[p ^ 1][j + 1][k + 1] = (f[p ^ 1][j + 1][k + 1] + F) % P;
if (R[i - j + 1] == R[i - k + 1])
f[p ^ 1][j][k] = (f[p ^ 1][j][k] + F) % P;
if (L[j + 1] == R[i - k + 1])
f[p ^ 1][j + 1][k] = (f[p ^ 1][j + 1][k] + F) % P;
if (R[i - j + 1] == L[k + 1])
f[p ^ 1][j][k + 1] = (f[p ^ 1][j][k + 1] + F) % P;
f[p][j][k] = 0;
}
printf("%d
",f[p][n][n]);
return 0;
}