【每日一题】【5月29日】管道取珠

题意：

有上下两个管道，上管道有 个球，下管道有 个球，每次可以从上管道或者下管道末尾取出一个球。
对每种最终取出的小球序列统计方案数。
记不同的序列数为 ，第 种序列的方案数为 。
显然有 。

需要你来计算 ，结果对 取模。

数据范围:

解法：

关键点：需要将求和式中的平方转化出来：视为两个相同的管道系统，独立取出小球，最终序列相同的方案数。

第 种序列方案数为 ，那么第一个和第二个均有 种方案，那么两者相同的方案数就是 。

对于类似的 次方，均可以按照这个思路转化一下。

视为两个系统取出小球，dp 求解就比较显然了。

表示两者都取出了 个小球，前者取出了上管道的 个小球，后者取出了下管道的 个小球。

（前者取出了下管道的 个小球，后者取出了下管道的 个小球）

dp 方程为：

数组空间比较大，可以采取滚动数组的技巧，缩减第一维的空间复杂度。

Code：

#include <bits/stdc++.h>
using namespace std;
const int N = 500 + 5;
const int mod = 1024523;
int dp[2][N][N], n, m;
char a[N], b[N];

int main() {
    cin >> n >> m;
    cin >> a + 1 >> b + 1;
    dp[0][0][0] = 1;
    for(int k = 1; k <= n + m; k++) {
        memset(dp[k&1], 0, sizeof dp[k&1]);
        for(int i = 0; i <= n; i++) {
            if(k - i < 0 || k - i > m) continue;
            for(int j = 0; j <= n; j++) {
                if(k - j < 0 || k - j > m) continue;
                auto update = [](int &x, int y) { x = (x + y) % mod; };
                if(i && j && a[i] == a[j]) update(dp[k & 1][i][j], dp[!(k & 1)][i - 1][j - 1]);
                if(i && k - j && a[i] == b[k - j]) update(dp[k & 1][i][j], dp[!(k & 1)][i - 1][j]);
                if(k - i && j && b[k - i] == a[j]) update(dp[k & 1][i][j], dp[!(k & 1)][i][j - 1]);
                if(k - i && k - j && b[k - i] == b[k-j]) update(dp[k & 1][i][j], dp[!(k & 1)][i][j]);
            }
        }
    }
    cout << dp[(n + m) & 1][n][n] << endl;
    return 0;
}