【-59】P1758 管道取珠[dp]

题目描述

管道取珠是小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早已知道,

Σai=C(n+m,n)

因此,小X希望计算得到:

Σ(ai)^2

你能帮助他计算这个值么?由于这个值可能很大,因此只需要输出该值对1024523的取模即可(即除以1024523的余数)。

说明:文中C(n+m,n)表示组合数。组合数C(a,b)等价于在a个不同的物品中选取b个的选取方案数。

img

输入输出格式

输入格式:

输入文件中的第一行为两个整数n,m,分别表示上下两个管道中球的数目。

第二行中为一个AB字符串,长度为n,表示上管道中从左到右球的类型。其中:A表示浅色球,B表示深色球。

第三行中为一个AB字符串,长度为m,表示下管道中的情形。

输出格式:

输出文件中仅一行为一个整数,即为 除以1024523的余数。

输入输出样例

输入样例#1:

1
2
3
2 1
AB
B

输出样例#1:

1
5

说明

【样例说明】

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

【数据规模和约定】

对于30%的数据,满足:$m,n<=12$;

对于100%的数据,满足:$m,n<=500$。

题解

由于是 $∑A_i^2$ ,可以看成取两次得到了相同的串的方案数。(想一想,为什么)

$ f [i][j][k][l]$ 表示第一次取A串中的前i个,取B串中的前j个,第二次取A串中的前k个,B串中的前l个的方案数

因为$k+l=i+j$ 所以最后一维可以省了.

然后用滚动数组.

转移方程就很好推了,见代码

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
59
#include<bits/stdc++.h>
using namespace std;
int read()
{
char s;
int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9'));
if(s==EOF)exit(0);
if(s=='-')base=-1,s=getchar();
while(s>='0'&&s<='9')
{
k=k*10+(s-'0');
s=getchar();
}
return k*base;
}
void write(int x)
{
if(x<0)
{
putchar('-');
write(-x);
}
else
{
if(x/10)write(x/10);
putchar(x%10+'0');
}
}
int n,m;
char a[510],b[510];
int f[5][510][510],t;//滚动数组
inline void add(int A,int &B)
{
B+=A;
if (B>1024523) B-=1024523;//取膜
}
int cur=0;
int main()
{
n=read();m=read();
scanf("%s",a+1);
scanf("%s",b+1);
f[0][0][0]=1;
for (int i=0;i<=n;i++,cur^=1)
for (int j=0;j<=m;j++)
for (int k=0;k<=n;k++)
{
t=f[cur][j][k];
if (i+j-k>m||i+j-k<0) continue;//越界退出
if (a[i+1]==a[k+1]) add(t,f[cur^1][j][k+1]);//状态转移
if (b[j+1]==b[i+j-k+1]) add(t,f[cur][j+1][k]);
if (a[i+1]==b[i+j-k+1]) add(t,f[cur^1][j][k]);
if (b[j+1]==a[k+1]) add(t,f[cur][j+1][k+1]);
f[cur][j][k]=0;//清掉
}
printf("%d",f[cur][m][n]);
return 0;
}