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

题意：

有上下两个管道，上管道有 $n$ 个球，下管道有 $m$ 个球，每次可以从上管道或者下管道末尾取出一个球。
对每种最终取出的小球序列统计方案数。
记不同的序列数为 $k$ ，第 $i$ 种序列的方案数为 $a_i$ 。
显然有 $\sum \limits_{i=1}^ka_i = C(n+m, n)$ 。

需要你来计算 $\sum \limits_{i=1}^ka_i^2$ ，结果对 $1024523$ 取模。

数据范围: $n, m \leq 500$

解法：

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

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

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

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

$dp[k][i][j]$ 表示两者都取出了 $k$ 个小球，前者取出了上管道的 $i$ 个小球，后者取出了下管道的 $j$ 个小球。

（前者取出了下管道的 $k - i$ 个小球，后者取出了下管道的 $k - j$ 个小球）

dp 方程为：

$dp[0][0][0] = 1$
$dp[k][i][j] += dp[k - 1][i - 1][j - 1] \space \space (a[i] == b[j])$
$dp[k][i][j] += dp[k - 1][i - 1][j] \space \space (a[i] == b[k - j])$
$dp[k][i][j] += dp[k - 1][i][j - 1] \space \space (b[k - i] == a[j])$
$dp[k][i][j] += dp[k - 1][i][j] \space \space (b[k - i] == b[k - j])$

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

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;
}