看到“P2159 [SHOI2009]舞会”这个标题估计不少人的第一反应和我一样舞会动态规划高精度这三样怎么凑到一起的没错这是一道经典的信息学竞赛题题面看起来像生活场景骨子里却是一个非常漂亮的组合计数问题。这里面的“DP”是动态规划Dynamic Programming不是显示器上的DP接口也不是显卡DP固件更不是DP转Type-C图像输出方案纯粹是算法里的老熟人。本题要求算出某种配对方案的数量数量级大到必须用高精度于是“DP 高精”就成了这题的核心标签。这篇文章我会从题意开始一步步拆解如何把舞会配对问题转化成排列计数再落到欧拉数递推最后给出一份可以直接AC的C高精度代码。无论你是备战竞赛还是想练一练动态规划和压位高精度这篇都值得收藏。1. 题意重述与解题思路总览1.1 题目到底让我们算什么题目大致是这样的有n个男生和n个女生他们的身高都互不相同。现在要求他们配成n对跳舞每一对恰好一男一女。问“恰好有k对是男生比女生高”的配对方案有多少种。这里的方案是完整的一对一匹配两个配对只要有一对舞伴不同就算不同方案。n的范围不会太大但也不小直接枚举所有匹配是n!种n稍微大一点就直接爆炸。比如n10n!已经是三百多万n20已经超过2×10^18连64位整数都装不下。所以这题的核心不是“枚举”而是“计数”。我第一次看到这题时第一反应是这不应该先按身高排序然后搞一个二维DP吗男生和女生的身高关系本质上就是比大小。比大小这种东西其实只和“排名”有关和具体身高值是多少厘米没有关系。只要两个人生高互不相同那么每一对的“谁高谁矮”就完全由男女生各自的身高排名决定。于是我们可以把每个人的具体身高压缩成一个编号这样问题就从“处理一堆身高数字”变成了“处理两组编号之间的排列关系”。1.2 为什么直接按身高DP不够方便有些同学可能会想把男生按身高从小到大排好女生也按身高从小到大排好然后dp[i][j]表示前i个男生和前j个女生匹配的方案数。这种思路看起来合理但碰到了一个麻烦男生i和女生j配对时到底算不算“男高”取决于i的身高是否大于j的身高。而两个数组是分别排序的男生i和女生j的排名差了就会产生交叉关系。如果我们同时枚举i和j状态维度是二维但匹配关系和“男高计数”会纠缠在一起转移时很难维护“恰好k对男高”这个约束。更关键的是配对是一一对应的男生选了一个女生这个女生就不能再选给其他男生。这本质上是一个“双射”问题而不是简单的子序列问题。所以我们需要换一个更高层的视角把整个配对方案看成一个排列。这个转化是解决本题的灵魂。2. 核心转化配对方案就是一个排列2.1 男生当位置女生当值把男生按身高从矮到高编号为1到n女生同样按身高从矮到高编号为1到n。那么任意一个配对方案都相当于给每个男生指定一个女生编号。我们定义排列π其中π[i]表示第i个男生的舞伴女生的编号。因为每人只能跳一次所以π是1到n的一个全排列。反过来任意一个全排列π也唯一确定一个配对方案。于是配对方案数从“n个男和n个女匹配”变成了“n个元素的排列”总数就是n!没有任何遗漏。现在看男高条件。第i个男生比他的舞伴女生高当且仅当男生的身高排名i大于女生编号π[i]也就是π[i] i。所以“恰好k对男高”就等价于排列π中满足π[i] i的位置i的个数恰好等于k。这个转化非常简洁而且一下子把具体身高完全扔掉。我们不需要关心男生身高是170还是180只需要知道他在所有男生里的排名。排序一次做完编号剩下的事情就是纯组合计数。2.2 从逆排列角度看这就是excedance计数π[i] i 这种条件看起来和“错排”有点像但又不完全是错排。我们再看一眼设σ是π的逆排列也就是σ[j]表示和第j个女生跳舞的男生编号。那么π[i] j i等价于σ[j] i j。也就是说一个配对中男生比女生高转化到逆排列里就变成了女生j对应的男生编号大于j。这种“值大于位置”的元素组合数学里有个专门的名字叫excedance超越数。一个排列中excedance的个数是一个经典计数对象。更妙的是排列中excedance个数的分布和下降数descent的分布完全相同也就是欧拉数。于是我们要求的就是欧拉数。拿n3验证一下。3个元素的全部排列有6个统计满足π[i]i的位置数排列ππ[1]1?π[2]2?π[3]3?男高对数123否否否0132否否是1213否是否1231否否是1312否是是2321否否是1分布是0对1种1对4种2对1种。这个数字恰恰是欧拉数A(3,0)1A(3,1)4A(3,2)1。看到这个结果思路基本就确定了。2.3 提醒一句别被“DP”热搜带偏有时候在网上搜“DP”出来的全是DisplayPort接口、DP转Type-C、英伟达DP固件什么的。这也不奇怪毕竟“DP”这组字母在硬件圈太火了。但在这道题里DP就是动态规划的全称Dynamic Programming。两者除了字母相同毫无关系。如果你是刷题时搜到这篇请放心后面提到的DP都是算法里的那个动态规划不会突然让你去接显示器。3. 动态规划推导欧拉数的递推公式3.1 经典递推A(n,k) (k1)A(n-1,k) (n-k)A(n-1,k-1)既然问题等价于求欧拉数我们直接用欧拉数的标准递推计算即可。设A(n,k)表示n个元素的排列中excedance个数也就是本题男高对数恰好为k的排列数量。递推式如下A(n,k) (k1) × A(n-1,k) (n-k) × A(n-1,k-1)边界条件A(0,0)1当k0或kn-1时A(n,k)0。这个递推初看有点莫名其妙系数怎么来的我简单解释一下。欧拉数虽然是按excedance定义的但它和“下降数”distribute相同。下降数指的是排列中满足π[i] π[i1]的位置i的个数。考虑从n-1个元素的排列插入最大元素n得到n个元素的排列。如果原来的排列有d个下降那么把n插进去下降数不变的位置有d1个下降数增加1的位置有n-1-d个。所以从A(n-1,d)转移到A(n,d)的系数是d1从A(n-1,d-1)转移到A(n,d)的系数是n-d。把d替换成k就得到上面的公式。至于“excedance个数和下降数个数同分布”这个结论是排列组合里的经典等分布结论。说起来又可以写一整篇这里不展开只需要知道它能用就行。你也可以把公式直接当作本题的DP转移来记忆从n-1到n新增一个“最大”的对象它要么不改变男高对数要么让男高对数加1两类情况的方案数分别就是那两个系数。3.2 用舞会的语言来理解系数虽然用欧拉数公式可以直接做题但为了加深印象我把系数映射回舞会场景再讲一遍。考虑从n-1对舞伴扩展到n对舞伴的过程我们把新来的最高男生和第n个女生各自性别中身高最高的同时加入。当然这里的“最高”是按各自性别内的排名说的不是绝对身高。如果前n-1对已经有j对男高那么新加入的两个人在最终匹配中会让男高对数保持不变或增加。保持不变的方式有j1种增加的方式有n-j种。这样解释可能有点抽象但本质上和插入元素n到下降间隔里的计数一模一样。所以我个人建议直接接受欧拉数递推把它当成一个已经证明好的结论来用把精力放在实现上。竞赛中很多组合计数题都这样关键是把模型识别出来而不是重新发明数学定理。3.3 边界条件与目标答案初始化A(0,0)1表示0个元素时没有excedance方案数为1。然后从i1到n逐层计算j的取值范围是0到i。注意j最大只能到i-1因为排列中位置1永远不可能满足π[1]1所以excedance个数最多是n-1。如果输入的k等于n答案直接是0。最终要输出的就是A(n,k)。这里有个自检方法对固定的nsum_{k0}^{n-1} A(n,k)必须等于n!。因为所有排列都会落在一个k上总数量当然等于全排列数。写代码的时候可以加个调试用的总和校验。3.4 再验证一组小数据我们计算n4的欧拉数。根据递推 A(4,0)1×A(3,0)1 A(4,1)2×A(3,1)(4-1)×A(3,0)2×43×111 A(4,2)3×A(3,2)(4-2)×A(3,1)3×12×411 A(4,3)4×A(3,3)(4-3)×A(3,2)011。所以分布是1,11,11,1总和244!正确。这个数字也验证了我们的转化没有出错。4. 高精度实现让数字飞一会儿4.1 为什么要自己写高精度欧拉数的增长速度虽然慢于n!但n200时A(200,100)这种中间值可能已经超过10^300远远超出任何64位整数范围。C标准库里没有大整数类所以我们需要自己实现一个简易的高精度方案。如果是在洛谷这类OJ上做题用Python倒是可以白嫖内置大整数但作为C选手手写高精度是基本功。而且本题的高精度并不复杂递推过程中只涉及“大数乘以小整数”和“大数相加”不需要做大数乘大数更不需要FFT。4.2 用vector 压位常见的高精度实现是十进制逐位存也就是每一位用一个int表示0-9。这样实现简单但空间浪费速度也慢。竞赛里推荐“压位”也就是把每9位十进制数打包成一个int基底BASE1000000000。这样vector的长度会缩小到原来的九分之一加法和乘法都快很多。压位的本质是换一个进制我们不使用10进制而是使用10^9进制。这个进制的每一位最大是999999999两个这样的数相乘再进位也不会超过int范围吗需要小心。乘法是大数每一位乘以一个普通整数乘积可能会超过int上限所以要用long long来存中间结果。例如当前位是999999999乘以系数200乘积是199999999800再加上进位仍然在long long范围内完全没问题。加法进位时因为两个小于10^9的数相加最大不超过2×10^9再加进位也不超过2×10^91还是int范围内但为了稳妥起见我们也可以用int或long long。下面代码里我用int足够。4.3 高精度加法与乘法的板子先看加法。两个大数从低位到高位逐位相加维护进位。注意两个数的长度可能不一样短的按0处理。const int BASE 1000000000; // 10^9 using BigInt vectorint; BigInt add(const BigInt a, const BigInt b) { int carry 0; int n max(a.size(), b.size()); BigInt c; for (int i 0; i n; i) { int sum carry; if (i (int)a.size()) sum a[i]; if (i (int)b.size()) sum b[i]; c.push_back(sum % BASE); carry sum / BASE; } if (carry) c.push_back(carry); return c; }再看乘法。这里只需要乘一个int也就是题目递推中的(k1)或(n-k)。乘法的核心是用long long存中间结果避免溢出。BigInt mul(const BigInt a, int m) { if (m 0) return BigInt{0}; long long carry 0; BigInt c; for (int v : a) { long long cur 1LL * v * m carry; c.push_back((int)(cur % BASE)); carry cur / BASE; } while (carry 0) { c.push_back((int)(carry % BASE)); carry / BASE; } return c; }输出的时候也要格外小心。vector里低位在前高位在后所以从后往前打印。除了最高位以外其他位如果不足9位前面要补零否则“1000000001”会打成“11”。void printBig(const BigInt a) { printf(%d, a.back()); for (int i (int)a.size() - 2; i 0; --i) { printf(%09d, a[i]); } printf(\n); }这几段板子基本是所有压位高精度题的通用模块建议直接背下来。5. 完整代码与运行效果5.1 可直接AC的C代码把DP递推和高精度板子拼起来就是下面这份完整代码。注释我写得比较详细关键的地方都有说明。#include bits/stdc.h using namespace std; const int BASE 1000000000; using BigInt vectorint; BigInt toBigInt(long long x) { if (x 0) return BigInt{0}; BigInt a; while (x 0) { a.push_back((int)(x % BASE)); x / BASE; } return a; } BigInt add(const BigInt a, const BigInt b) { int carry 0; int n max(a.size(), b.size()); BigInt c; for (int i 0; i n; i) { int sum carry; if (i (int)a.size()) sum a[i]; if (i (int)b.size()) sum b[i]; c.push_back(sum % BASE); carry sum / BASE; } if (carry) c.push_back(carry); return c; } BigInt mul(const BigInt a, int m) { if (m 0) return BigInt{0}; long long carry 0; BigInt c; for (int v : a) { long long cur 1LL * v * m carry; c.push_back((int)(cur % BASE)); carry cur / BASE; } while (carry 0) { c.push_back((int)(carry % BASE)); carry / BASE; } return c; } void printBig(const BigInt a) { if (a.empty()) { printf(0\n); return; } printf(%d, a.back()); for (int i (int)a.size() - 2; i 0; --i) { printf(%09d, a[i]); } printf(\n); } int main() { int n, k; if (scanf(%d%d, n, k) ! 2) return 0; // dp[i][j] 表示 i 个元素的排列中excedance个数为 j 的方案数 vectorvectorBigInt dp(n 1, vectorBigInt(n 1, toBigInt(0))); dp[0][0] toBigInt(1); for (int i 1; i n; i) { for (int j 0; j i; j) { BigInt val toBigInt(0); // A(i-1, j) - A(i, j)系数 j1 if (j i - 1) { val add(val, mul(dp[i - 1][j], j 1)); } // A(i-1, j-1) - A(i, j)系数 i-j if (j 1) { val add(val, mul(dp[i - 1][j - 1], i - j)); } dp[i][j] val; } } if (k 0 || k n - 1) { printf(0\n); } else { printBig(dp[n][k]); } return 0; }这份代码的核心就在双重循环内部。第一项对应“加入新元素后excedance数不变”的转移第二项对应“加入新元素后excedance数加1”的转移。两个系数的含义在前面已经解释过。5.2 本地测试与自检方法我建议拿到代码先测几组小数据跟手算结果对照n3k0输出1k1输出4k2输出1。n4k1输出11。任何n如果k0输出永远是1。这个可以理解所有元素都不超过自己的位置只有严格递增排列123...n一种所以是1。任何n如果kn输出0。还有一个更稳的测试把输出所有k的和看看是不是n!。比如n5欧拉数分布是1,26,66,26,1总和1205!。你可以临时在主函数里加一个循环求和验证高精度加法是否正确。5.3 复杂度分析状态数是O(n^2)。每个状态做一次大数乘小整数和一次大数加法大数位数大约是O(n log n)量级。整体时间复杂度上界可以写成O(n^3 log n)听起来有点吓人但n只有200左右时跑起来非常快本地VSCode一秒都用不了。空间方面如果直接用二维vector存所有dp[i][j]会存下矩阵里的每个高精度数。n200时状态数约4万每个数平均几十个int内存占用可能在几十MB量级OJ上通常能过。如果卡内存可以改成滚动数组因为递推只用到了上一行。不过对本题来说二维写法更直观不容易出错内存也够用没必要强行优化。6. 踩坑记录与实战经验6.1 这题最容易踩的4个坑第一个坑是“k的范围”。很多人以为k可以等于n但事实上排列π里位置1永远不可能有π[1]1所以最大男高对数只能是n-1。输入可能给你一个很大的k不要慌直接特判输出0。第二个坑是“输出补零”。压位高精度输出最容易错的地方就是中间的几组前导零。比如大数存储是[1, 234567890, 1]实际数字是1000000001234567890? 不对反了。我们存的是低位在前所以a[2]1, a[1]234567890, a[0]1数字是1 234567890 000000001。如果打印时中间不补零会变成12345678901直接就错了。所以从高位开始打印时除了最高位其余位一律用%09d补满9位。第三个坑是“乘法系数为0”。递推第二项里系数i-j当ji时为0所以A(n,n)0。mul函数开头要判断m0直接返回0否则如果a是空vector会发生奇怪的问题。我把所有大数初始化为{0}可以避免空vector索引越界。第四个坑是“高精加法进位的顺序”。压位加法要从低位到高位vector下标0是低位。如果反过来处理进位方向全乱。写的时候最好注释清楚免得过两天自己都看不懂。6.2 如果题目改成“至少k对”有些变体问题会问“男高对不少于k”的方案数。这时候不需要重新推导DP只需要在得到整行欧拉数后做一个后缀和ans sum_{jk}^{n-1} dp[n][j]。因为欧拉数分布的性质这个后缀和也可以用高精度加法轻松得到。注意如果k为负数理论上不会就变成全排列数n!。如果题目进一步要求输出概率也就是方案数除以n!那就更复杂了。因为高精度下无法方便地做浮点除法通常需要额外实现大数除法或者改用模意义下的DP。不过在SHOI2009原题里只要求输出方案数所以我们不需要处理。6.3 欧拉数的其他求法什么时候用欧拉数除了上面的O(n^2)递推还有生成函数、整式递推等高级方法。如果n特别大比如n10^5并且答案对质数取模可以用卷积或多项式求逆在O(n log n)内求出整行欧拉数。但本题要求高精度而且n不大O(n^2)高精度递推就是最简单可靠的选择。另外如果题目允许Python直接用Python写会非常轻松因为Python的int天生支持任意精度只需要把上面的DP用Python写一遍代码短一半。但C选手练习高精度从来不是坏事毕竟很多题目都得靠这套板子。我个人建议把add和mul当成模板背下来以后遇到“DP结果巨大”的题直接套。6.4 一点实战心得最后说点我自己的体会。这题真正难的其实不是高精度而是“把配对看成排列”这层转化。我第一次做的时候卡在“如何维护男生女生同时匹配”的状态上绕了大半天。后来在纸上画了几组小数据突然意识到每个男生最终一定只对应一个女生这不就是排列吗一旦看出这一点后面的欧拉数递推就是顺水推舟。所以遇到计数类DP不要急着设状态。先把问题数学化看看能不能用排列、组合、图论这类已知模型来描述。很多时候模型转化做得好DP方程就自然浮出水面。P2159这道题虽然老但知识点非常综合排序、排列、组合恒等式、动态规划、高精度全串在了一个“舞会”壳里。把它吃透比盲目刷十道同类型的题都管用。