[Leaf] [P1758] 管道取珠

luogu-p1758-管道取珠">Luogu-P1758 管道取珠

1. 题面梗概

中译中: 两个管道 $A$ 和 $B$ 分别装有珠子。每次从其中一个管道取一个珠子，直到取完。不同的取法可能产生相同的颜色序列。设第 $i$ 种颜色序列产生的次数为 $a_i$，求 $\sum a_i^2$。

2. 逻辑推导

这题最反直觉的就是这个平方和，如果直接数序列，那绝对是死路一条。

2.1 普通DP

我们尝试用普通的DP计数：

定义 $f[i][j]$ 为从 $A$ 取 $i$ 个，从 $B$ 取 $j$ 个产生的方案数，但是问题来了，这个 $f$ 只能算出来到达某个状态的总方案数，对于具体的数没法处理，也就是无助于平方和。

而全部序列总共有：$\binom{n+m}{n}$ 个，天文数字，复杂度直接进行一个大爆炸，此路不通，我们需要换个角度分析。

2.2 平方？

我们重新回到这个 $\sum a_i^2$。在组合数学中， $x^2$ 可以拆写成 $x \times x$，而什么是 $a_i \times a_i$？

$a_i$ 是产生颜色序列 $S_i$ 的方案数。那么 $a_i \times a_i$ 就可以换个角度理解：甲和乙两个人独立进行取珠游戏，最终产生的颜色序列恰好都是 $S_i$ 的方案数。

那么 $\sum a_i$ 就是：甲乙两个人独立游戏，只要他们最终的颜色一样，就算一种合法方案，求总方案数。

2.3 双人模型

现在我们考虑同时计数，保证两人在每一步取出的珠子颜色都相同。捋一捋我们有什么状态：总共取了几个珠子；甲从 A 取了几个；甲从 B 取了几个；乙从 A 取了几个；乙从 B 取了几个。

综合定义：$f[k][i_1][i_2]$ 表示总共拿了 $k$ 个珠子，甲从 A 拿了 $i_1$ 个（ 从 B 拿了 $k-i_1$ 个 ），乙从 A 拿了 $i_2$ 个，从 $B$ 拿了 $k - i_2$ 个。

接着考虑转移：$k$ 范围 $0 \to n + m$。每一时刻，甲乙各有两种取法，一共就是 4 种，而只有两人选出的珠子颜色一样时，转移才生效。

那么就很简单了，我们把这个组合数级别的复杂度降解为了 $O((N+M) \cdot N^2)$ 复杂度的 DP 问题。

注意到 $k$ 状态只取决于 $k-1$ 的状态，因此我们不必保留整个 DP 数组，使用滚动数组进行优化。

3. 代码实现

▶

AcCode

#include<bits/stdc++.h>
using namespace std;

const int mod = 1024523;
const int maxn = 500 + 50;

int dp[2][maxn][maxn];
int cur, nxt;
int m, n;
string s1, s2;

void add( int a, int b, int val )
{
    dp[nxt][a][b] = ( dp[nxt][a][b] + val ) % mod;
}

int main()
{	
    cin >> n >> m;
    cin >> s1 >> s2;

    s1 = ' ' + s1;
    s2 = ' ' + s2;

    dp[0][0][0] = 1;

    for( int k = 0; k < n + m; ++ k )
    {
        cur = ( k & 1 );
        nxt = ( k + 1 ) & 1;
        memset( dp[nxt], 0, sizeof( dp[nxt] ) );

        int l = max( 0 , k - m );
        int r = min( n , k );

        for( int i = l; i <= r; ++ i )
        {
            for( int j = l; j <= r; ++ j )
            {
                if( !dp[cur][i][j] ) continue;
                int _i = k - i, _j = k - j;
                int val = dp[cur][i][j];

                if( i < n && j < n && s1[i+1] == s1[j+1] ) 
                    add( i+1, j+1, val );    
                if( i < n && _j < m && s1[i+1] == s2[_j+1] )
                    add( i+1, j, val );
                if( _i < m && j < n && s2[_i+1] == s1[j+1] )
                    add( i, j+1, val );
                if( _i < m && _j < m && s2[_i+1] == s2[_j+1] )
                    add( i, j, val );
                
            }
        }
    }

    cout << dp[(n + m) & 1][n][n] << '\n';

    return 0;
}

4. 复盘

• 复杂度: $O( (N+M) \cdot N^2 )$。空间 $O( N^2 )$。

• 碎碎念: 这种思维方式我个人理解为组合意义。如果遇到求 $\sum a_i^2$ 或者 $\sum a_i^3$ 的计数题，可以往$k$ 个人同时做游戏上靠。

• 关联笔记: [[计数DP]]