管道取珠

https://ac.nowcoder.com/acm/problem/17621

题意：链接：https://ac.nowcoder.com/acm/problem/17621
来源：牛客网

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

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

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

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

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

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

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

因此，小X希望计算得到

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

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

思路：我们可以想像是二个游戏装置为同一种类序列的种数，所以用dp[k][i][j]表示序列长度为k时第一个装置上管道取i个，第二个装置上管道取j个时的相同种类数；我们可以很容易得出转化方程
s为上管道从右到左的序列，x为下管道从右到左的序列
dp[k][i][j]+=dp[k-1][i-1] [j-1] (s[i]=s[j])
dp[k][i][j]+=dp[k-1][i-1][j] (s[i]=x[k-j])
dp[k][i][j]+=dp[k-1][i][j-1] (x[k-i]=s[j])
dp[k][i][j]+=dp[k-1][i][j] (x[k-i]=x[k-j])
初始化dp[0][0][0]=1;
我们发现转化方程第一个下标中的k只与上一个(k-1)有关,所以可以用滚动数组节约空间；

代码：

#include<bits/stdc++.h>
#define ll long long
#define inf 1024523

using namespace std;

inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

ll dp[2][1005][1005];

int main()
{
    int n, m;
    char s[10005], x[10005];
    cin >> n >> m;
    scanf("%s",s+1);
    for(int i=1,j=n;i<j;i++,j--)
    {
        swap(s[i],s[j]);
    }
    scanf("%s",x+1);
    for(int i=1,j=m;i<j;i++,j--)
    {
        swap(x[i],x[j]);
    }
    dp[0][0][0]=1;
    for(int k=1;k<=n+m;k++)
    {
        for(int i=0;i<=k;i++)
        {
            if(k-i>m||i>n)
            {
                continue;
            }
            for(int j=0;j<=k;j++)
            {
                if(k-j>m||j>n)
                {
                    continue;
                }
                dp[k%2][i][j]=0;
                if(i!=0&&j!=0&&i<=n&&j<=n&&s[i]==s[j])
                {
                    dp[k%2][i][j]+=dp[(k-1)%2][i-1][j-1];
                }
                if(i!=0&&k-j!=0&&i<=n&&k-j<=m&&s[i]==x[k-j])
                {
                    dp[k%2][i][j]+=dp[(k-1)%2][i-1][j];
                }
                if(k-i!=0&&j!=0&&k-i<=m&&j<=n&&x[k-i]==s[j])
                {
                    dp[k%2][i][j]+=dp[(k-1)%2][i][j-1];
                }
                if(k-i!=0&&k-j!=0&&k-i<=m&&k-j<=m&&x[k-i]==x[k-j])
                {
                    dp[k%2][i][j]+=dp[(k-1)%2][i][j];
                }
                dp[k%2][i][j]=dp[k%2][i][j]%inf;
            }
        }
    }
    cout << dp[(n+m)%2][n][n] << endl;
    return 0;
}