「BZOJ1566」[NOI2009]管道取珠

Description

管道取珠是小X很喜欢的一款游戏。在本题中,我们将考虑该游戏的一个简单改版。游戏画面如图11所示:

游戏初始时,左侧上下两个管道分别有一定数量的小球(有深色球和浅色球两种类型),而右侧输出管道为空。每一次操作,可以从左侧选择一个管道,并将该管道中最右侧的球推入右边输出管道。
例如,我们首先从下管道中移一个球到输出管道中,将得到图2所示的情况。

假设上管道中有nn个球, 下管道中有mm个球,则整个游戏过程需要进行n+mn + m次操作,即将所有左侧管道中的球移入输出管道。最终n+mn + m个球在输出管道中从右到左形成输出序列。
爱好数学的小X知道,他共有Cn+mnC_{n+m}^n种不同的操作方式,而不同的操作方式可能导致相同的输出序列。举个例子,对于图33所示的游戏情形:

我们用A表示浅色球,B表示深色球。并设移动上管道右侧球的操作为U, 移动下管道右侧球的操作为D,则共有C2+11=3C_{2+1}^1=3种不同的操作方式, 分别为UUD, UDU, DUU;最终在输出管道中形成的输出序列(从右到左)分别为BABBBABBA。可以发现后两种操作方式将得到同样的输出序列。
假设最终可能产生的不同种类的输出序列共有KK种,其中第ii种输出序列的产生方式(即不同的操作方式数目)有aia_i个。聪明的小X早已知道,

i=1kai=Cn+mn\sum_{i=1}^k a_i=C_{n+m}^n

因此,小X希望计算得到

i=1kai2\sum_{i=1}^k a_i^2

你能帮助他计算这个值么?由于这个值可能很大,因此只需要输出该值对10245231024523的取模即可(即除以10245231024523的余数)。
说明:文中Cn+mnC_{n + m}^n表示组合数。组合数CabC_a^b等价于在aa个不同的物品中选取bb个的选取方案数。

Input

第一行包含两个整数nn, mm,分别表示上下两个管道中球的数目。
第二行为一个AB字符串,长度为nn,表示上管道中从左到右球的类型。其中A表示浅色球,B表示深色球。
第三行为一个AB字符串,长度为mm,表示下管道中的情形。

Output

i=1kai2\sum_{i=1}^k a_i^2除以10245231024523的余数。

Sample Input

1
2
3
2 1
AB
B

Sample Output

1
5

HINT

30%30\%的数据满足 n,m12n, m \leq 12
100%100\%的数据满足n,m500n, m \leq 500

Solution

ai\sum a_i似乎不好求。
ai2\sum a_i^2就是两个人分别取长度为n+mn+m的序列,取出序列相同的方案数。
fi,j,kf_{i,j,k}表示取到第ii个,AA取了上面的jj个,BB取了上面的kk个。
xjb转移一下就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}

/*
f[i][j][j]
取了前i个,A在上面取j个,B在上面取k个
*/
const int N = 510;
int f[2][N][N];
int n, m;
char s[N], t[N];
const int p = 1024523;
void add(int &x, int v) {
x += v;
if(x >= p) x %= p;
}
int main() {
n = read(), m = read();
scanf("%s%s",s+1,t+1);
for(int i = 1; i <= n / 2; ++i) swap(s[i], s[n - i + 1]);
for(int i = 1; i <= m / 2; ++i) swap(t[i], t[m - i + 1]);
bool c = 0;
f[0][0][0] = 1;
int x, y;
for(int i = 1; i <= n + m; ++i) {
c ^= 1;
memset(f[c],0,sizeof f[c]);
for(int j = 0; j <= n && j <= i; ++j)
for(int k = 0; k <= n && k <= i; ++k) {
x = i - j;
y = i - k;
if(x < 0 || y < 0 || x > m || y > m) continue;
if(s[j] == s[k] && j > 0 && k > 0) add(f[c][j][k], f[c ^ 1][j - 1][k - 1]); //上上
if(t[x] == t[y]) add(f[c][j][k], f[c ^ 1][j][k]);// 下下
if(s[j] == t[y] && j > 0) add(f[c][j][k], f[c ^ 1][j - 1][k]);//上下
if(t[x] == s[k] && k > 0) add(f[c][j][k], f[c ^ 1][j][k - 1]);//下上
}
}
writeln(f[c][n][n]);
return 0;
}