CF1716F Bags with Balls 题解

· · 题解

洛谷传送门： CF1716F Bags with Balls

暴力推式子大法好

题目实际上就是让我们求：

\sum_{i=0}^{n} i^k \binom{n}{i} \left( \left \lceil \frac{m}{2} \right \rceil \right)^i \left( \left \lfloor \frac{m}{2} \right \rfloor \right)^{n-i}

即枚举奇数编号球的个数，计算对应的方案数。

式子中的 i^k 很难搞，考虑将普通幂转为下降幂，因为下降幂与组合数相乘能把底数从求和变量换成常量，结果很好看：

\begin{aligned} x^k &= \sum_{i=0}^{k} \begin{Bmatrix} k\\i \end{Bmatrix}x^{\underline i}\\ \binom{n}{x}x^{\underline k} &= \binom{n-k}{x-k}n^{\underline k} \end{aligned}

剩下的过程就非常顺畅了，一步到位：

\begin{aligned} &\sum_{i=0}^{n} i^k \binom{n}{i} \left( \left \lceil \frac{m}{2} \right \rceil \right)^i \left( \left \lfloor \frac{m}{2} \right \rfloor \right)^{n-i}\\ = &\sum_{i=0}^n \binom{n}{i} \left( \left \lceil \frac{m}{2} \right \rceil \right)^i \left( \left \lfloor \frac{m}{2} \right \rfloor \right)^{n-i} \sum_{j=0}^k \begin{Bmatrix} k\\j \end{Bmatrix}i^{\underline j}\\ = &\sum_{i=0}^n \sum_{j=0}^k \begin{Bmatrix} k\\j \end{Bmatrix} \binom{n-j}{i-j} n^{\underline j} \left( \left \lceil \frac{m}{2} \right \rceil \right)^i \left( \left \lfloor \frac{m}{2} \right \rfloor \right)^{n-i}\\ = &\sum_{j=0}^k \begin{Bmatrix} k\\j \end{Bmatrix} n^{\underline j} \sum_{i=0}^n \binom{n-j}{n-i} \left( \left \lceil \frac{m}{2} \right \rceil \right)^i \left( \left \lfloor \frac{m}{2} \right \rfloor \right)^{n-i}\\ = &\sum_{j=0}^k \begin{Bmatrix} k\\j \end{Bmatrix} n^{\underline j} \sum_{i=0}^{n-j} \binom{n-j}{i} \left( \left \lceil \frac{m}{2} \right \rceil \right)^{n-i} \left( \left \lfloor \frac{m}{2} \right \rfloor \right)^{i}\\ = &\sum_{j=0}^k \begin{Bmatrix} k\\j \end{Bmatrix} n^{\underline j} \left( \left \lceil \frac{m}{2} \right \rceil \right)^{j}m^{n-j}\\ \end{aligned}

最后一步将 n-i 替换为 i 并使用了二项式定理化简。现在我们就可以做到 O(k^2) 预处理第二类斯特林数，O(k) 查询了（注意不要写成 O(k \log n) 查询，会T）。

代码：

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

typedef long long ll;
const int Mod = 998244353;
const int MAXN = 2005;

ll n, m, k;
ll S[MAXN][MAXN];

inline int qpow(int a, int b) {
    ll base = a, ans = 1;
    while (b) {
        if (b & 1) ans = ans * base % Mod;
        base = base * base % Mod;
        b >>= 1;
    }
    return ans;
}

void solve() {
    scanf("%d%d%d", &n, &m, &k);

    int ans = 0;
    ll a1 = 1, a2 = 1, a3 = qpow(m, n), inv = qpow(m, Mod - 2);
    for (int j = 1; j <= min(k, n); j++) {
        a1 = a1 * ((m + 1) / 2) % Mod;
        a2 = a2 * (n - j + 1) % Mod;
        a3 = a3 * inv % Mod;
        ans = (ans + S[k][j] * a1 % Mod * a2 % Mod * a3) % Mod;
    }
    printf("%d\n", ans);
}

int main() {
    S[0][0] = 1;
    for (int i = 1; i < MAXN; i++)
        for (int j = 1; j <= i; j++)
            S[i][j] = (S[i - 1][j - 1] + j * S[i - 1][j]) % Mod;

    int T;
    scanf("%d", &T);
    while (T--) {
        solve();
    }
    return 0;
}