NOI2009管道取珠

2014年12月17日2,1140

Description

Input

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

Output

仅包含一行,即为 Sigma(Ai^2) i从1到k 除以1024523的余数。

Sample Input

2 1
AB
B

Sample Output

5

HINT

样例即为文中(图3)。共有两种不同的输出序列形式,序列BAB有1种产生方式,而序列BBA有2种产生方式,因此答案为5。
【大致数据规模】
约30%的数据满足 n, m ≤ 12;
约100%的数据满足n, m ≤ 500。

题解

这题怎么想的。。。

byvoid:

状态F[i1,j1,i2,j2]可以表示为取珠方法X状态为(i1,j1),取珠方法Y状态为(i2,j2),X,Y的输出序列相同的有序对(X,Y)的数量。设U[i]为上管道第i个珠子,L[i]为下管道第j个珠子。则状态F[i1,j1,i2,j2]可以更新的状态

clip_image002

由于X,Y应当同步,所以当i1,j1,i2都确定以后j2可以被表示为i1 + j1 – i2,于是状态表示可以减少一维。