NOI2009 管道取数

题目:

  管道取珠是小X很喜欢的一款游戏。在本题中,我们将考虑该游戏的一个简单改版。游戏画面如图1所示:
  游戏初始时,左侧上下两个管道分别有一定数量的小球(有深色球和浅色球两种类型),而右侧输出管道为空。每一次操作,可以从左侧选择一个管道,并将该管道中最右侧的球推入右边输出管道。
  假设上管道中有 个球, 下管道中有 个球,则整个游戏过程需要进行 次操作,即将所有左侧管道中的球移入输出管道。最终 个球在输出管道中从右到左形成输出序列。
  爱好数学的小X知道,他共有 种不同的操作方式,而不同的操作方式可能导致相同的输出序列。
  假设最终可能产生的不同种类的输出序列共有 种,其中:第 种输出序列的产生方式(即不同的操作方式数目)有 个。聪明的小X早已知道:
  因此,小X希望计算得到:
  你能帮助他计算这个值么?由于这个值可能很大,因此只需要输出该值对 的取模即可(即除以 的余数)。
  说明:文中 表示组合数。组合数 等价于在 个不同的物品中选取 个的选取方案数。
  

思路:

  对于 一个比较套路的做法就是转化成相同种类的操作方式对数。那么就可以看成两个人在同时玩两个游戏,求两人玩出相同输出序列的方案数。
  那么之间记录 表示两人上下排的剩余个数,因为 ,所以只要记录 就能表达一个状态,再滚动优化一下空间就能过了。复杂度

代码:

#include <bits/stdc++.h>
#define File(_) freopen(#_ ".in", "r", stdin), freopen(#_ ".out", "w", stdout)
#define ALL(x) x.begin(), x.end()
#define mset(a, b) memset(a, b, sizeof a)
#define rep(i, a, b) for(int i(a), i##_END_(b); i <= i##_END_; i++) 
#define drep(i, a, b) for(int i(a), i##_END_(b); i >= i##_END_; i--)
using namespace std;
template<class T> inline bool tomax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<class T> inline bool tomin(T &a, T b) {return b < a ? a = b, 1 : 0;}
typedef long long ll;
typedef double db;

const int N = 505, MOD = 1024523;

char s1[N], s2[N];
int n, m;

int dp[2][N][N];

int main() {
    File(ball);
    scanf("%d%d", &n, &m);
    scanf("%s%s", s1 + 1, s2 + 1);
    rep(a, 0, n) {
        mset(dp[a & 1], 0);
        rep(b, 0, m) rep(c, 0, min(a + b, n))  {
            int &ans = dp[a & 1][b][c];
            if(a + b == 0) {ans = 1; continue;}
            int d = a + b - c;
            if(a != 0 && c != 0 && s1[a] == s1[c]) (ans += dp[a - 1 & 1][b][c - 1]) %= MOD;
            if(b != 0 && c != 0 && s2[b] == s1[c]) (ans += dp[a & 1][b - 1][c - 1]) %= MOD;
            if(a != 0 && d != 0 && s1[a] == s2[d]) (ans += dp[a - 1 & 1][b][c]) %= MOD;
            if(b != 0 && d != 0 && s2[b] == s2[d]) (ans += dp[a & 1][b - 1][c]) %= MOD;
        }
    }
    printf("%d\n", dp[n & 1][m][n]);
    return 0;
}