CF2025E Card Game (动态规划、多项式快速幂、银牌题)

Question

CF2025E Card Game (opens new window)

Solution

可以把牌的匹配看成是括号匹配，A 玩家拿的牌看成左括号，B 玩家拿的牌看成右括号

如果只考虑一种花色的话，一个合理的括号匹配恰好对应一种括号序列

但是这里一共有 $n$ 种花色，需要第 $1$ 种花色多出 $k$ 个左括号，剩下的 $n-1$ 种花色一共多出 $k$ 个右括号才能匹配

所以我们这里需要求出一种花色多出 $k$ 个左括号的方案数，由于对称性，这个数也等于一种花色多出 $k$ 个右括号的方案数

这个问题可以用 dp 来解决，定义 $dp[i][j]$ 表示前 $i$ 个括号，左括号比右括号多出 $j$ 个的方案数，那么很容易可以推出转移方程

$dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1]$

于是答案就是 $dp[m][k]$ ，我们令 $f=dp[m]$

那么如何求 $\sum_{i=2}^n k_i=K$ 满足的方案数，把 $f$ 看成多项式，这里刚好满足多项式乘法的定义，于是我们把 $f^{n-1}$ 就得到了 $n-1$ 个花色，一共有 $k$ 个左括号多出来的方案数了

最后枚举 $k$ 累计答案就可以了，答案为 $\sum_{k=0}^m f[k]\times f^{n-1}[k]$

Code

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

Z f[N][N], g[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, m;
    cin >> n >> m;

    f[0][0] = 1;
    for (int i = 1; i <= m; i++) {
        f[i][0] = f[i - 1][1];
        for (int j = 1; j <= i; j++)
            f[i][j] = f[i - 1][j - 1] + f[i - 1][j + 1];
    }
    
    for (int i = 0; i <= m; i++)
        if (1) g[i] = f[m][i];
    
    Poly F; F.resize(m + 1);
    for (int i = 0; i <= m; i++) F[i] = g[i];

    F = F.pow(n - 1, m + 1);

    Z ans = 0;
    for (int i = 0; i <= m; i++) {
        Z now = F[i] * g[i];
        ans += now;
    }

    cout << ans << '\n';

    return 0;
}