P1758 [NOI2009]管道取珠

    • 266通过
    • 881提交
  • 题目提供者 洛谷OnlineJudge
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 字符串 递推 NOI系列 2009 高性能
  • 难度 省选/NOI-
  • 时空限制 2000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    管道取珠是小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个的选取方案数。

    输入输出格式

    输入格式:

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

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

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

    输出格式:

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

    输入输出样例

    输入样例#1: 复制
    2 1
    AB
    B
    
    输出样例#1: 复制
    5

    说明

    【样例说明】

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

    【数据规模和约定】

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

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

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。