Michael_Bryant最喜欢的G(al)G(ame)

那些悲伤,那些寂寞,那些几乎让自己放弃生活的希望的痛苦的回忆,绝对绝对不要将它们忘记。

Michael_Bryant最喜欢的番剧

抱歉⋯我已经绝对不可能再获得幸福了,因为⋯我发现⋯ 其实我⋯ 早就已经被幸福包围了

Michael_Bryant正在看的番剧

死亡一点也不温柔,只有无尽的黑暗和孤独。 就算联系得再紧密,人也是孤独的。

bzoj 1566: [NOI2009]管道取珠

题目链接

传送门

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。

题解

考虑DP
题意相同类型的序列有x个,对答案贡献是x^2。
等价于两个人各自进行操作,得到相同类型序列的方案数.
这个东西是比较好证的。
我们设一个合法序列状态是A,并且现在有x,y两种取法均能得到A
根据乘法原理,那么问题就转化为求A(x,y)二元组的个数.
想象一下现在有两个人正在取数,要求两个人取数相同的方案个数.
首先考虑到的是四维DP
用dp[i][j][k][l]表示两个人分别从上下取到了i,j,k,l个珠子
然后发现当你知道了i,j,k之后l的数值就显然了
这个时候你可以删除一维
people1和people2都取了i+j个数的相同方案的方案个数。
然后枚举上一次取的位置转移即可。。
这个时候你可以轻松在bzoj上面AC
然而luogu的内存是128MB
这之后你看看dp式子 发现dp[i]只能由i-1和i转移
考虑滚动数组
从而成功AC

三维DP朴素代码

三维滚动数组DP代码

写在最后

就不要吐槽我int* p这种代码习惯了好伐

Add a Comment

电子邮件地址不会被公开。 必填项已用*标注

隐藏