476 字
2 分钟
范德蒙德卷积 (Vandermonde's Convolution)
范德蒙德卷积 (Vandermonde’s Convolution)
1. 核心恒等式
2. 组合意义证明
考虑一个大小为 的集合,其中前 个元素标记为红色,后 个元素标记为蓝色。 从这 个元素中任意选取 个元素的总方案数为 。 若按选出的红色元素个数 分类(),则需要从 个红色中选 个,同时从 个蓝色中选 个,方案数为 。 对所有可能的 求和,二者必然相等。
3. 常用推论与变形
- 对称平方和:
- 上指标求和 (朱世杰恒等式):
- 带权范德蒙德卷积:
4. 竞赛实战应用:二重计数化简模板
在很多组合计数问题中,面对形如 的二重求和,直接计算为 ;使用范德蒙德卷积可化简为单次 的组合数 查询。
#include <bits/stdc++.h>using namespace std;using ll = long long;const int MOD = 998244353;const int N = 200005;ll fac[N], ifac[N];ll qpow(ll a, ll b) { ll res = 1; while (b) { if (b & 1) res = res * a % MOD; a = a * a % MOD; b >>= 1; } return res;}void init_comb(int n) { fac[0] = 1; for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % MOD; ifac[n] = qpow(fac[n], MOD - 2); for (int i = n; i >= 1; i--) ifac[i - 1] = ifac[i] * i % MOD;}ll C(int n, int m) { if (m < 0 || m > n) return 0; return fac[n] * ifac[m] % MOD * ifac[n - m] % MOD;}// 范德蒙德卷积求和:sum_{k=0}^r C(m, k) * C(n, r-k) = C(m+n, r)ll vandermonde(int m, int n, int r) { if (r < 0 || r > m + n) return 0; return C(m + n, r);}范德蒙德卷积 (Vandermonde's Convolution)
https://sanzenin.top/posts/obsidian/范德蒙德卷积/分享文章
生成精美分享图或复制链接,与更多人分享本文。
继续阅读
换条路线
从其他文章中稳定抽取
最后更新于 ,距今已过 74 天
部分内容可能已过时