[Luogu P1758] [BZOJ 1566] [NOI2009]管道取珠

洛谷传送门

BZOJ传送门

题目描述

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

（图1）

游戏初始时，左侧上下两个管道分别有一定数量的小球（有深色球和浅色球两种类型），而右侧输出管道为空。每一次操作，可以从左侧选择一个管道，并将该管道中最右侧的球推入右边输出管道。

例如：我们首先从下管道中移一个球到输出管道中，将得到图2所示的情况。

（图2）

假设上管道中有n$n$个球, 下管道中有m$m$个球，则整个游戏过程需要进行n+m$n+m$次操作，即将所有左侧管道中的球移入输出管道。最终n+m$n+m$个球在输出管道中从右到左形成输出序列。

爱好数学的小X知道，他共有C(n+m，n)$C(n+m，n)$种不同的操作方式，而不同的操作方式可能导致相同的输出序列。举个例子，对于图3所示的游戏情形：

（图3）

我们用A$A$表示浅色球，B$B$表示深色球。并设移动上管道右侧球的操作为U$U$，移动下管道右侧球的操作为D$D$，则共有C(2+1，1)=3$C(2+1，1)=3$种不同的操作方式，分别为UUD$UUD$，UDU$UDU$，DUU$DUU$；最终在输出管道中形成的输出序列（从右到左）分别为BAB$BAB$，BBA$BBA$，BBA$BBA$。可以发现后两种操作方式将得到同样的输出序列。

假设最终可能产生的不同种类的输出序列共有K$K$种，其中：第i$i$种输出序列的产生方式（即不同的操作方式数目）有ai$a_i$个。聪明的小X$X$早已知道，

Σai=C(n+m,n)$\Sigma a_i=C(n+m,n)$

因此，小X希望计算得到：

Σ(ai)2$\Sigma (a_i{)}^2$

你能帮助他计算这个值么？由于这个值可能很大，因此只需要输出该值对1024523$1024523$的取模即可（即除以1024523$1024523$的余数）。

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

输入输出格式

输入格式：

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

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

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

输出格式：

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

输入输出样例

输入样例#1：

2 1
AB
B

输出样例#1：

5

说明

【样例说明】

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

【数据规模和约定】

对于30%的数据，满足：m，n≤12$m，n\le 12$；

对于100%的数据，满足：m，n≤500$m，n\le 500$。

解题分析

dp$dp$神题， ∑a2i$\sum a_i^2$相当于取两次， 形成序列相同的方案数。

那么设dp[i][j][k][l]$dp[i][j][k][l]$表示第一次第一个字符串取了前i$i$个， 第二个字符串取了前j$j$个， 第二次第一个字符串取了前k$k$个， 第二个字符串取了前l$l$个。 因为i+j=k+l$i+j=k+l$， 所以可以省略最后一维。

初始状态dp[0][0][0]=1$dp[0][0][0]=1$， 最后的答案为dp[i][j][k]$dp[i][j][k]$。

然而空间不支持O(N3)$O(N^3)$， 所以我们把第一维滚动。

取模取多了还会T….

代码如下：

#include <cstdio>
using namespace std;
#define R register
#define IN inline
#define W while
#define MX 505
#define MOD 1024523
int dp[2][MX][MX];
char a[MX], b[MX];
IN void add(int &tar, R int x) {tar += x; if(tar > MOD) tar -= MOD;}
int main(void)
{
    int len1, len2;
    scanf("%d%d", &len1, &len2);
    scanf("%s%s", a + 1, b + 1);
    dp[0][0][0] = 1; R int i, j, k, cur = 0, val;
    for (i = 0; i <= len1; ++i, cur ^= 1)
    for (j = 0; j <= len2; ++j)
    for (k = 0; k <= len1; ++k)
    {
        val = dp[cur][j][k];
        if(i + j - k < 0 || i + j - k > len2) continue;
        if(a[i + 1] == a[k + 1]) add(dp[cur ^ 1][j][k + 1], val);
        if(a[i + 1] == b[i + j - k + 1]) add(dp[cur ^ 1][j][k], val);
        if(b[j + 1] == a[k + 1]) add(dp[cur][j + 1][k + 1] ,val);
        if(b[j + 1] == b[i + j - k + 1]) add(dp[cur][j + 1][k], val);
        dp[cur][j][k] = 0;
    }
    printf("%d", dp[cur][len2][len1]);
}