a187: NOI2009 Day2.2.管道取珠
Tags :
Accepted rate : 10人/13人 ( 77% ) [非即時]
評分方式:
Tolerant

最近更新 : 2014-11-01 03:22

Content

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

 

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

 

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

 

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

 

ki=1 Ai = C(n+m,n)


因此,小X希望计算得到

 

ki=1 Ai2


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

Input

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

Output

仅包含一行,即为

ki=1 Ai2

除以1024523的余数。

Sample Input
2 1
AB
B
Sample Output
5
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (10%): 2.0s , <1K
公開 測資點#1 (10%): 2.0s , <1K
公開 測資點#2 (10%): 2.0s , <1K
公開 測資點#3 (10%): 2.0s , <1K
公開 測資點#4 (10%): 2.0s , <1K
公開 測資點#5 (10%): 2.0s , <1K
公開 測資點#6 (10%): 2.0s , <1K
公開 測資點#7 (10%): 2.0s , <1K
公開 測資點#8 (10%): 2.0s , <1K
公開 測資點#9 (10%): 2.0s , <1K
Hint :

【样例说明】

样例即为文中(3)。共有两种不同的输出序列形式,序列BAB1种产生方式,而序列BBA2种产生方式,因此答案为5

【大致数据规模】

30%的数据满足 n, m ≤ 12

100%的数据满足n, m ≤ 500


感谢david942j提醒!
Tags:
出處:
NOI2009Day2第二题 [管理者:
liouzhou_101 (王启圣)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」