第一次在洛谷见到 P2159 [SHOI2009]舞会 的时候我第一反应是这不就是个排序贪心把男生女生身高排一下统计一下比某个女生高的男生数量乘一下不就行了。实际动手才发现完全不是那么回事这道题的核心是 DP 和高精而且是两个东西缺一不可DP 解决的是“恰好 k 对满足身高关系”的配对计数高精是因为答案规模直接到阶乘级别200 个人的配对方案数远超 64 位整数。这篇文章我会把完整的思考链路写出来为什么不能直接乘、为什么女生要从高到低处理、钦定 DP 的转移是怎么来的、最后怎么用二项式反演把“钦定”变成“恰好”以及一套可直接提交的压位高精度模板。1. 先把题读懂这是一道带约束的完美匹配计数1.1 题目到底让你算什么题目背景是舞会有 n 位先生和 n 位女士身高都给定。现在要求男女两两配对配成 n 对舞伴。定义一对舞伴“和谐”当且仅当男士身高严格大于女士身高。题目要求输出恰好有 k 对和谐舞伴的配对方案数。注意几个关键词第一是“恰好 k 对”不是“至少 k 对”也不是“最多 k 对”第二是“配对方案数”也就是说完整的 n 对都算在内不能只挑 k 对出来第三是“男 女”这个比较方向很多题解会写成“男比女高”如果原题方向相反只需要把男女数组交换一下结论完全一样。先看一个最小例子帮助理解。n2男生身高 [170, 180]女生身高 [160, 175]。所有配对只有两种175 女生配 180 男生160 女生配 170 男生两对都是男高女矮和谐对数为 2175 女生配 170 男生160 女生配 180 男生只有 160 女生那一对和谐和谐对数为 1。所以答案是k1 时输出 1k2 时输出 1k0 时输出 0。如果没有这套手算作为基准后面写出 DP 和反演公式时很容易出错而不知道错在哪。1.2 为什么答案会大到必须上高精度不取模直接输出一个十进制大整数这是这道题区别于一般 DP 计数题的地方。所有配对方案总数是 n!。n200 时200! 大约是 3.8×10^374任何一个 64 位整数都装不下。即使是满足约束条件的子集数量级也在阶乘附近不可能用 long long 或者 __int128 解决。所以标题里的“高精”不是附加题而是必须实现的一部分。后面我会给出一套只包含加法、减法、乘法的精简 BigInt因为这道题不需要除法也不需要取模写起来比完整高精度模板要短得多。1.3 这道题训练了什么从算法层面看这道题的价值有三层用排序让计数集合产生“包含关系”从而设计出干净的 DP 转移用“钦定 DP 二项式反演”把“恰好 k 对”转换成“钦定 j 对再任意配对”的问题用压位 BigInt 处理阶乘量级的答案同时保证性能。这里面最容易让人卡住的不是高精度而是第二步的二项式反演。很多人 DP 写出了 f[i][j]却不知道怎么把“选 j 个和谐对”变成“恰好 k 个”然后就去看题解看完觉得公式很简单自己再写又总是符号反、下标错。下面我会把每一步为什么这样做讲清楚。2. 核心观察按女生从高到低处理可选集合是嵌套的2.1 女生排序后的可选集合性质先把所有女生按身高从高到低排序记为 g_1 ≥ g_2 ≥ ... ≥ g_n。对第 i 个女生定义她的“可取高男集合”S_i { 男生 m | m g_i }集合大小记为 a_i。由于 g_1 ≥ g_2所以“严格大于 g_1”的男生集合一定包含在“严格大于 g_2”的男生集合里。换句话说序列 S_1, S_2, ..., S_n 是单调递增的S_1 ⊆ S_2 ⊆ ... ⊆ S_n对应地a_1 ≤ a_2 ≤ ... ≤ a_n。这个包含关系是整个 DP 能成立的根本原因。如果女生按从低到高处理这个性质就反过来了后面的转移会变得非常麻烦。下面我用一个例子说明为什么方向不能反。2.2 为什么从低到高不行从高到低就行假设男生身高 [160, 170, 180]女生身高 [165, 175]。如果按女生从低到高处理165 女生可以选比她高的男生170 或 180共 2 个175 女生可以选比她高的男生只有 180共 1 个。如果在处理 175 女生时前面 165 女生已经选走了 180那么 175 女生就没得选如果前面选走的是 170那么 175 还有 180 可选。也就是说前面消耗的“高男生”是否落在当前女生可选集合里取决于具体选了谁。仅仅记录“已经选了 j 个和谐对”是不够的。现在把女生从高到低处理175 女生先选她可选集合是 {180}数量 1165 女生后选她可选集合是 {170, 180}数量 2。关键点在于175 女生无论选哪个男生她选的男生一定大于 175因此也一定大于 165。也就是说前面女生消耗的男生必然落在当前女生更矮的可选集合里。于是处理到当前女生时她的可选数量就可以简单地写成 a_i - (j-1)其中 j-1 是前面已经钦定和谐配对的个数。这正是“按身高从高到低处理”的威力集合嵌套的方向让前面的消耗能直接扣减。2.3 先设计一个子问题只分配“钦定和谐对”定义状态f[i][j] 表示处理前 i 个女生从高到低从中选出 j 个女生并为这 j 个女生各分配一个“比自己高”的男生且男生互不相同的方案数。注意这个状态里其余的女生先不分配男生只有被选中的 j 个“钦定和谐对”会占用男生。这样设计是因为后面还要考虑剩余 n-j 对任意配对所以 DP 阶段没必要处理全部配对。转移方程f[i][j] f[i-1][j] f[i-1][j-1] × (a_i - (j-1))其中 a_i 是第 i 个女生可选的高男生数量j-1 是前 i-1 个女生中已经被选中并分配了高男生的对数。转移的第一项很好理解第 i 个女生不入选钦定和谐对。第二项说明第 i 个女生入选前面 j-1 个钦定对占用的男生因为女生身高顺序的关系必然都在当前女生的可选集合 S_i 中所以当前女生还能选 a_i - (j-1) 个男生。如果 a_i - (j-1) ≤ 0那么贡献为 0写代码时需要判断。边界条件是 f[0][0] 1f[0][j] 0j 0。用刚才 n2 的例子验证一下。女生从高到低是 [175, 160]男生 [170, 180]所以 a_1 1180a_2 2170, 180。f[0][0] 1处理第一个女生 175f[1][0] 1f[1][1] f[0][0] × (1 - 0) 1处理第二个女生 160f[2][0] 1f[2][1] f[1][1] f[1][0] × 2 1 2 3f[2][2] f[1][1] × (2 - 1) 1。f[2][2] 1 表示两个女生都钦定为和谐对时只有一种分配方案175 配 180160 配 170。f[2][1] 3 表示只钦定一个和谐对时三种情况选 175 女生配 180或选 160 女生配 180或选 160 女生配 170。这些结果和直觉一致。这里强调一下如果原题要求“男士不低于女士”也就是身高相等也算和谐只需要把统计 a_i 时的“严格大于”换成“大于等于”。排序后的包含关系依然成立因为相等身高女生的可选集合相同仍然是子集关系DP 完全不用改。3. 从“钦定 j 对”到“恰好 k 对”二项式反演3.1 补上剩下的任意配对f[n][j] 算出来之后钦定了 j 个和谐对并且这 j 对的具体男生已经分配好了。剩下的 n-j 个女生和 n-j 个男生可以任意配对每种任意配对都计入 G[j]。所以定义G[j] f[n][j] × (n-j)!为什么是 (n-j)! 而不是别的因为选定 j 个钦定对之后剩下的女生集合是确定的剩下的男生集合也是确定的。任意配对就是让这 n-j 个女生去对应 n-j 个男生的一个排列方案数自然是 (n-j)!。注意这里“任意配对”是真正意义上的任意不限制剩下的配对是否和谐。于是 G[j] 实际上表示钦定某 j 对一定和谐其余 n-j 对随便配这样的总方案数。3.2 G[j] 和真实答案 A[i] 的关系设 A[i] 表示恰好有 i 个和谐对的完整配对方案数。现在思考一个恰好有 i 个和谐对的方案会被 G[j] 重复计数多少次给定一个真实有 i 个和谐对的配对方案要让它被计进 G[j]我们需要从这个方案里选出 j 个真实和谐对作为“钦定和谐对”。有多少种选法从 i 个和谐对中选 j 个数量是 C(i, j)。剩下的 n-j 对在这个方案里本来就是确定的(n-j)! 的任意配对中包含这个方案的剩余部分。因此G[j] Σ_{ij}^{n} C(i, j) × A[i]这个式子非常像一个“已知上三角矩阵和反求向量”的问题。G[j] 是钦定 j 对的方案数它包含了所有真实和谐对数 i ≥ j 的贡献且贡献系数是 C(i, j)。3.3 反演公式与手算验证利用二项式反演从 G[j] 恢复 A[k]A[k] Σ_{jk}^{n} (-1)^{j-k} × C(j, k) × G[j]这个公式初学者很容易记错符号或下标。我的记忆方式是G[j] 是“钦定 j 对”A[k] 是“恰好 k 对”反演时仍然从大到小枚举 j系数是 C(j, k)也就是从 j 个钦定对里选出 k 个作为“恰好”的对象符号由 j-k 的奇偶性决定。继续用 n2 的例子验证。已经算出了 f[2][0]1f[2][1]3f[2][2]1阶乘 fact[0]1fact[1]1fact[2]2所以G[0] 1 × 2 2G[1] 3 × 1 3G[2] 1 × 1 1。反演A[0] G[0] - C(1,0)G[1] C(2,0)G[2] 2 - 3 1 0A[1] G[1] - C(2,1)G[2] 3 - 2 1A[2] G[2] 1。结果和 1.1 节手算完全一致和谐对数为 0 的方案数为 0为 1 和 2 的方案数各为 1。这一步验证非常重要因为整套公式只要有一处符号或系数写错最终的 A[k] 就会是负数或者明显不合理的大数。4. 高精度 BigInt 实现加法、减法、乘法足矣4.1 需要哪些运算这道题里高精度参与的地方有运算触发场景是否必须高精度 高精度DP 转移 f[i-1][j] ...组合数递推反演累加必须高精度 - 高精度反演中的符号项必须高精度 × 高精度G[j] f[n][j] × (n-j)!以及反演中的 C(j,k) × G[j]必须高精度 × 小整数DP 转移中乘 (a_i - (j-1))阶乘递推可用高精度×高精度替代但单独优化更快除法、取模无不需要所以可以写一个精简 BigInt内部用 vector 压位存储支持比较、加减乘、输出即可。4.2 压位设计我通常用 base 100000000也就是 1e8每个 int 存 0 到 99999999。数字按小端序存储即低位在前。为什么不用 1e9两个 1e9 量级的数相乘接近 1e18再加上进位和中间累加虽然 long long 上限约 9.2e18 也能扛住但为了安全用 1e8 会让乘法中间值稳定在 1e16 级别几乎没有溢出风险。代价只是每个数字多一两个 vector 元素对 n ≤ 200 的题量级来说完全无所谓。输出时要特别注意前导零。base 1e8说明除了最高位之外每个 vector 元素输出时都要用 setw(8) 和 setfill(0) 补零。4.3 BigInt 类模板#include bits/stdc.h using namespace std; struct BigInt { static const int BASE 100000000; static const int WIDTH 8; vectorint d; // 小端序每个元素 [0, BASE) bool neg false; BigInt(long long x 0) { if (x 0) { neg true; x -x; } if (x 0) d.push_back(0); while (x 0) { d.push_back(x % BASE); x / BASE; } } void trim() { while (d.size() 1 d.back() 0) d.pop_back(); if (d.size() 1 d[0] 0) neg false; } bool isZero() const { return d.size() 1 d[0] 0; } bool operator(const BigInt o) const { if (neg ! o.neg) return neg; if (!neg) { if (d.size() ! o.d.size()) return d.size() o.d.size(); for (int i (int)d.size() - 1; i 0; --i) if (d[i] ! o.d[i]) return d[i] o.d[i]; return false; } else { if (d.size() ! o.d.size()) return d.size() o.d.size(); for (int i (int)d.size() - 1; i 0; --i) if (d[i] ! o.d[i]) return d[i] o.d[i]; return false; } } BigInt operator-() const { BigInt res *this; if (!res.isZero()) res.neg !res.neg; return res; } BigInt operator(const BigInt o) const { if (neg o.neg) { BigInt res; res.neg neg; int carry 0; int n max(d.size(), o.d.size()); for (int i 0; i n || carry; i) { int cur carry; if (i (int)d.size()) cur d[i]; if (i (int)o.d.size()) cur o.d[i]; if (cur BASE) { cur - BASE; carry 1; } else carry 0; res.d.push_back(cur); } res.trim(); return res; } if (neg) return o - (-(*this)); return *this - (-o); } BigInt operator-(const BigInt o) const { if (neg ! o.neg) return *this (-o); if (neg) return (-o) - (-(*this)); if (*this o) return -(o - *this); BigInt res; int borrow 0; int n d.size(); res.d.resize(n); for (int i 0; i n; i) { int cur d[i] - borrow; if (i (int)o.d.size()) cur - o.d[i]; if (cur 0) { cur BASE; borrow 1; } else borrow 0; res.d[i] cur; } res.trim(); return res; } BigInt operator*(const BigInt o) const { if (isZero() || o.isZero()) return BigInt(0); BigInt res; res.neg neg ^ o.neg; res.d.assign(d.size() o.d.size(), 0); for (int i 0; i (int)d.size(); i) { long long carry 0; for (int j 0; j (int)o.d.size() || carry; j) { long long cur res.d[i j] carry; if (j (int)o.d.size()) cur 1LL * d[i] * o.d[j]; res.d[i j] cur % BASE; carry cur / BASE; } } res.trim(); return res; } }; ostream operator(ostream out, const BigInt x) { if (x.neg) out -; out x.d.back(); for (int i (int)x.d.size() - 2; i 0; --i) out setw(8) setfill(0) x.d[i]; return out; }这段代码有几个容易写错的细节第一trim 里一定要处理零的符号否则 -0 会出现第二减法里两个负数的情况直接通过取负转换比硬写负数的借位简单很多第三乘法里 res.d 的初值要全部置 0否则累加会出错。5. 完整 AC 代码与手算验证5.1 主流程主流程分成五步读入、排序和统计、DP、组合数与阶乘、反演输出。int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin n k; if (k 0 || k n) { cout 0 \n; return 0; } vectorint male(n), female(n); for (int i 0; i n; i) cin male[i]; for (int i 0; i n; i) cin female[i]; sort(male.begin(), male.end()); // 女生从高到低排序 sort(female.begin(), female.end(), greaterint()); // cnt[i] 表示比第 i 个女生高的男生数量也就是 a_i vectorint cnt(n); for (int i 0; i n; i) { // 严格大于用 upper_bound cnt[i] male.end() - upper_bound(male.begin(), male.end(), female[i]); } // 阶乘 vectorBigInt fact(n 1); fact[0] BigInt(1); for (int i 1; i n; i) fact[i] fact[i - 1] * BigInt(i); // 组合数 C[n][k] vectorvectorBigInt C(n 1, vectorBigInt(n 1)); for (int i 0; i n; i) { C[i][0] C[i][i] BigInt(1); for (int j 1; j i; j) C[i][j] C[i - 1][j - 1] C[i - 1][j]; } // DP滚动数组f[n][j] 最终存在 dp[j] vectorBigInt dp(n 1); dp[0] BigInt(1); // f[0][0] 1 for (int i 1; i n; i) { int limit cnt[i - 1]; for (int j i; j 1; --j) { int ways limit - (j - 1); if (ways 0) { dp[j] dp[j] dp[j - 1] * BigInt(ways); } } // dp[0] 保持为 1因为 f[i][0] 始终是 1 } // 二项式反演求 A[k] BigInt ans; for (int j k; j n; j) { BigInt term C[j][k] * dp[j] * fact[n - j]; if ((j - k) 1) ans ans - term; else ans ans term; } cout ans \n; return 0; }这段代码里 DP 用的是滚动数组倒序枚举 j 保证 dp[j-1] 还是上一轮的值。dp[j] dp[j-1] * ways 时dp[j] 里保留的是上一轮的 f[i-1][j]加上当前女生入选后的贡献正确。dp[0] 不需要改因为 f[i][0] 恒等于 1。反演里的 term 我合并了三部分C[j][k]、dp[j]也就是 f[n][j]、fact[n-j]。注意 dp[j] 一定要在 DP 全部结束后再取不能在半路取否则滚动数组的值不是最终的 f[n][j]。5.2 用手算结果验证代码逻辑用 n2 的例子过一遍男生排序后 [170, 180]女生从高到低 [175, 160]。cnt[0] 1180 大于 175cnt[1] 2170 和 180 都大于 160。DP 过程初始 dp[0] 1i1limit1j1ways 1 - 0 1dp[1] 0 1×1 1i2limit2j2ways 2 - 1 1dp[2] 0 dp[1]×1 1j1ways 2 - 0 2dp[1] 1 dp[0]×2 3。所以 dp[0]1dp[1]3dp[2]1与前面的 f 数组一致。事实上有更简单的验证方式n1 时如果男生比女生高那么 k1 答案应该是 1k0 答案应该是 0如果男生比女生矮那么 k0 答案应该是 1k1 答案应该是 0。用这个边界数据去测代码能很快暴露 DP 方向和反演的符号错误。5.3 边界情况与特殊数据第一k 越界。如果输入 k 0 或 k n直接输出 0。虽然实际数据不一定给这种输入但写上没坏处。第二所有身高都一样。如果题目要求严格大于那么任意配对中和谐对数量都是 0也就是说 A[0] n!A[k0] 0。由于严格大于不存在cnt[i] 全为 0DP 会给出 dp[0] 1dp[j0] 0反演结果 G[0] n!最终 A[0] n!。如果题目要求不矮于则所有配对都和谐A[n] n!其他为 0。这个差异完全由 upper_bound 还是 lower_bound 决定。第三女生全部高于男生。此时所有配对都不和谐A[0] n!其他为 0。代码里 cnt[i] 0DP 后 dp[j0] 0再反演也会得到同样结论。第四男生存在身高相等的情况。因为 upper_bound 找的是严格大于当前女生的第一个位置所以女生身高中间的重复不会影响集合嵌套关系DP 依然正确。唯一要注意的是排序方式女生排序用 greater () 降序男生排序用默认升序这是题解里最常见的固定写法。6. 我踩过的坑希望你别再踩6.1 排序方向写反这是最容易犯的错。第一次写这题我很自然地按女生从低到高排序因为很多“男生比女生高”的题都是这么做的。结果 DP 转移里 a_i - (j-1) 怎么算都觉得怪手算小样例发现答案对不上。后来才意识到这种“前面选的男生必然在当前女生可选集合里”的性质只在高到低方向成立。如果从低到高处理前面选的和谐男生可能在当前女生的可选集合之外也可能在里面必须额外记录具体状态状态数直接爆炸。所以看到这种有“可选集合随排序单调变化”的计数题先停下来想想按哪个方向处理才能保证前面的消耗都能被直接扣减排序方向不是美学问题是转移能否成立的问题。6.2 upper_bound 和 lower_bound 用混严格大于用 upper_bound大于等于用 lower_bound。这个细节看题解时很容易忽略自己写的时候经常顺手用 lower_bound导致身高相等的数据全错。如果原题要求男士比女士高那相等身高不算和谐必须用 upper_bound。我习惯在代码旁边写一行注释// 严格大于upper_bound防止改数据范围时手滑。6.3 反演公式的系数写反二项式反演有两种常见形式方向不一样。这道题用的是A[k] Σ_{jk}^{n} (-1)^{j-k} C(j,k) G[j]写代码时重要的是 C(j,k) 而不是 C(k,j)组合数的两个参数顺序反了小样例可能看不出来n 大一点答案就会变得很奇怪。我自己的检查方法是先用小样例手算 A[0]、A[1]、A[2]如果能对上再上大数据。6.4 BigInt 减法借位和负数处理BigInt 减法里如果处理不到位最容易出两个问题一是结果为负数时符号丢了二是前导零没有清除干净导致输出 000123 这种错误。我上面的模板用if (*this o) return -(o - *this)巧妙地统一了正负号处理但在实际题目里如果怕减法实现有 bug也可以用另一种思路反演时把正的项和负的项分别累加最后输出绝对值大的减去绝对值小的。6.5 高精度拷贝导致不必要的时间开销n 最多 200 的时候直接按值传 BigInt 问题不大。但如果 n 到了 300 或 500DP 里的高精度对象拷贝会很浪费。建议在可能传大对象的地方用常量引用例如 operator 和 operator* 的参数都写成 const BigInt。另外乘小整数可以单独提供一个 mulSmall(int x) 函数避免走通用 BigInt 乘法那一层循环虽然通用乘法也能过但能省则省。7. 个人经验这题最该记住的套路我个人做完这题之后最大的收获不是高精度模板而是“钦定 反演”这套组合。以后再遇到“恰好 k 个满足条件”的计数问题我会优先想如果改成“钦定 j 个满足条件其余任意”问题是不是就好解决多了如果是那就可以用二项式反演把答案转回来。这道题里钦定 j 个和谐对之后剩下的 n-j 对任意配问题立刻变得非常简单因为任意配就是阶乘。这种美感和“排序让集合嵌套”的构造比高精度本身更值得记住。实际写题时我建议你多备几个小样例尤其是 n1 和 n2 的边界。先把答案手算出来再跑代码。如果小样例过了再试全部相等、全部相等但严格大于、男女全部反转这些极端数据。最后再提交。这样能省下至少半天调试时间。