题目
题目描述
管道取珠是小X很喜欢的一款游戏。在本题中，我们将考虑该游戏的一个简单改版。游戏画面如图1所示：
游戏初始时，左侧上下两个管道分别有一定数量的小球（有深色球和浅色球两种类型），而右侧输出管道为空。每一次操作，可以从左侧选择一个管道，并将该管道中最右侧的球推入右边输出管道。
例如：我们首先从下管道中移一个球到输出管道中，将得到图2所示的情况。
假设上管道中有$n$个球, 下管道中有$m$个球，则整个游戏过程需要进行$n+m$次操作，即将所有左侧管道中的球移入输出管道。最终$n+m$个球在输出管道中从右到左形成输出序列。
爱好数学的小X知道，他共有C(n+m，n)种不同的操作方式，而不同的操作方式可能导致相同的输出序列。举个例子，对于图3所示的游戏情形：
我们用A表示浅色球，B表示深色球。并设移动上管道右侧球的操作为U，移动下管道右侧球的操作为D，则共有C(2+1，1)=3种不同的操作方式，分别为UUD，UDU，DUU；最终在输出管道中形成的输出序列（从右到左）分别为BAB，BBA，BBA。可以发现后两种操作方式将得到同样的输出序列。
假设最终可能产生的不同种类的输出序列共有K种，其中：第i种输出序列的产生方式（即不同的操作方式数目）有ai个。聪明的小X早已知道，
Σai=C(n+m,n)
因此，小X希望计算得到：
Σ(ai)^2
你能帮助他计算这个值么？由于这个值可能很大，因此只需要输出该值对1024523的取模即可（即除以1024523的余数）。
说明：文中C(n+m，n)表示组合数。组合数C(a，b)等价于在a个不同的物品中选取b个的选取方案数。
输入输出格式
输入格式：
输入文件中的第一行为两个整数n，m，分别表示上下两个管道中球的数目。
第二行中为一个AB字符串，长度为n，表示上管道中从左到右球的类型。其中：A表示浅色球，B表示深色球。
第三行中为一个AB字符串，长度为m，表示下管道中的情形。
输出格式：
输出文件中仅一行为一个整数，即为 除以1024523的余数。
输入输出样例
输入样例#1：
2 1
AB
B
输出样例#1：
5
说明
【样例说明】
样例即为文中（图3）。共有两种不同的输出序列形式，序列BAB有1种产生方式，而序列BBA有2种产生方式，因此答案为5。
【数据规模和约定】
对于30%的数据，满足：m，n<=12；
对于100%的数据，满足：m，n<=500。
题解
恶心好题
首先$\sum_{1}^{k}{ai}^{2}$这个玩意得转换一下
怎么转换呢？
根据题目中的定义，$ai$是第$i$种输出序列的产生方式（即不同的操作方式数目）
那么我们能把${ai}^{2}$看成是两个人玩这个游戏，两个人取出第i种输出序列的方法的组合（乘法原理）
然后考虑$dp$
既然是两个人，$f_{i,j,k,l}$表示第一个人第一个管道取前$i$个，第二个管道取前$j$个，第二个人第一个管道取前$k$个，第二个管道取前$l$个
然后你会发现$n,m\le 500$，空间炸了
为了使两个人取出的序列相同，前提是取得一样多，所以$i+j=k+l$
所以可以优化掉一维
然而在bzoj上这样已经可以过了，但$luogu$上空间还是炸
发现$f_i$是由$f_i$或$f_{i-1}$递推过来的
所以可以用滚动数组优化空间到$n^2$
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# define LL long long
using namespace std;
const int MAX=505;//这里要开大点不然会RE
const LL mod=1024523;
int n,m;
string a,b;
LL f[2][MAX][MAX];
bool fl;
int read()
{
int x=0;
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
string Read()
{
string a="";
char ch=getchar();
for(;ch!='B'&&ch!='A';ch=getchar());
for(;ch=='B'||ch=='A';a+=ch,ch=getchar());
return a;
}
int main()
{
n=read(),m=read(),a=Read(),b=Read();
f[0][0][0]=1;
for(int i=0;i<=n;++i)
{
for(int j=0;j<=m;++j)
for(int k=0;k<=n;++k)
{
if(i+j-k>m||i+j-k<0) continue;
if(a[i]==a[k]) f[fl^1][j][k+1]=(f[fl^1][j][k+1]+f[fl][j][k])%mod;
if(b[j]==b[i+j-k]) f[fl][j+1][k]=(f[fl][j+1][k]+f[fl][j][k])%mod;
if(a[i]==b[i+j-k]) f[fl^1][j][k]=(f[fl^1][j][k]+f[fl][j][k])%mod;
if(a[k]==b[j]) f[fl][j+1][k+1]=(f[fl][j+1][k+1]+f[fl][j][k])%mod;
f[fl][j][k]=0;
}
fl^=1;
}
printf("%lld",f[fl][m][n]);
return 0;
}
