企业官网建设流程全解析

看到“P2159 [SHOI2009]舞会”这个标题，估计不少人的第一反应和我一样：舞会？动态规划？高精度？这三样怎么凑到一起的？没错，这是一道经典的信息学竞赛题，题面看起来像生活场景，骨子里却是一个非常漂亮的组合计数问题。这里面的“DP”是动态规划（Dynamic Programming），不是显示器上的DP接口，也不是显卡DP固件，更不是DP转Type-C图像输出方案，纯粹是算法里的老熟人。本题要求算出某种配对方案的数量，数量级大到必须用高精度，于是“DP + 高精”就成了这题的核心标签。这篇文章我会从题意开始，一步步拆解如何把舞会配对问题转化成排列计数，再落到欧拉数递推，最后给出一份可以直接AC的C++高精度代码。无论你是备战竞赛，还是想练一练动态规划和压位高精度，这篇都值得收藏。

1. 题意重述与解题思路总览

1.1 题目到底让我们算什么

题目大致是这样的：有n个男生和n个女生，他们的身高都互不相同。现在要求他们配成n对跳舞，每一对恰好一男一女。问“恰好有k对是男生比女生高”的配对方案有多少种。这里的方案是完整的一对一匹配，两个配对只要有一对舞伴不同，就算不同方案。

n的范围不会太大，但也不小，直接枚举所有匹配是n!种，n稍微大一点就直接爆炸。比如n=10，n!已经是三百多万；n=20，已经超过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）的分布完全相同，也就是欧拉数。于是我们要求的就是欧拉数。

拿n=3验证一下。3个元素的全部排列有6个，统计满足π[i]<i的位置数：

分布是：0对1种，1对4种，2对1种。这个数字恰恰是欧拉数A(3,0)=1，A(3,1)=4，A(3,2)=1。看到这个结果，思路基本就确定了。

2.3 提醒一句，别被“DP”热搜带偏

有时候在网上搜“DP”，出来的全是DisplayPort接口、DP转Type-C、英伟达DP固件什么的。这也不奇怪，毕竟“DP”这组字母在硬件圈太火了。但在这道题里，DP就是动态规划的全称Dynamic Programming。两者除了字母相同，毫无关系。如果你是刷题时搜到这篇，请放心，后面提到的DP都是算法里的那个动态规划，不会突然让你去接显示器。

3. 动态规划推导：欧拉数的递推公式

3.1 经典递推：A(n,k) = (k+1)A(n-1,k) + (n-k)A(n-1,k-1)

既然问题等价于求欧拉数，我们直接用欧拉数的标准递推计算即可。设A(n,k)表示n个元素的排列中，excedance个数（也就是本题男高对数）恰好为k的排列数量。递推式如下：

A(n,k) = (k+1) × A(n-1,k) + (n-k) × A(n-1,k-1)

边界条件：A(0,0)=1；当k<0或k>n-1时，A(n,k)=0。

这个递推初看有点莫名其妙，系数怎么来的？我简单解释一下。欧拉数虽然是按excedance定义的，但它和“下降数”distribute相同。下降数指的是排列中满足π[i] > π[i+1]的位置i的个数。考虑从n-1个元素的排列插入最大元素n，得到n个元素的排列。如果原来的排列有d个下降，那么把n插进去，下降数不变的位置有d+1个，下降数增加1的位置有n-1-d个。所以从A(n-1,d)转移到A(n,d)的系数是d+1，从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对男高，那么新加入的两个人在最终匹配中会让男高对数保持不变或增加。保持不变的方式有j+1种，增加的方式有n-j种。这样解释可能有点抽象，但本质上和插入元素n到下降间隔里的计数一模一样。所以我个人建议：直接接受欧拉数递推，把它当成一个已经证明好的结论来用，把精力放在实现上。竞赛中很多组合计数题都这样，关键是把模型识别出来，而不是重新发明数学定理。

3.3 边界条件与目标答案

初始化A(0,0)=1，表示0个元素时，没有excedance，方案数为1。然后从i=1到n逐层计算，j的取值范围是0到i。注意j最大只能到i-1，因为排列中位置1永远不可能满足π[1]<1，所以excedance个数最多是n-1。如果输入的k等于n，答案直接是0。

最终要输出的就是A(n,k)。这里有个自检方法：对固定的n，sum_{k=0}^{n-1} A(n,k)必须等于n!。因为所有排列都会落在一个k上，总数量当然等于全排列数。写代码的时候可以加个调试用的总和校验。

3.4 再验证一组小数据

我们计算n=4的欧拉数。根据递推： A(4,0)=1×A(3,0)=1； A(4,1)=2×A(3,1)+(4-1)×A(3,0)=2×4+3×1=11； A(4,2)=3×A(3,2)+(4-2)×A(3,1)=3×1+2×4=11； A(4,3)=4×A(3,3)+(4-3)×A(3,2)=0+1=1。

所以分布是1,11,11,1，总和24=4!，正确。这个数字也验证了我们的转化没有出错。

4. 高精度实现：让数字飞一会儿

4.1 为什么要自己写高精度

欧拉数的增长速度虽然慢于n!，但n=200时，A(200,100)这种中间值可能已经超过10^300，远远超出任何64位整数范围。C++标准库里没有大整数类，所以我们需要自己实现一个简易的高精度方案。

如果是在洛谷这类OJ上做题，用Python倒是可以白嫖内置大整数，但作为C++选手，手写高精度是基本功。而且本题的高精度并不复杂：递推过程中只涉及“大数乘以小整数”和“大数相加”，不需要做大数乘大数，更不需要FFT。

4.2 用vector 压位

常见的高精度实现是十进制逐位存，也就是每一位用一个int表示0-9。这样实现简单，但空间浪费，速度也慢。竞赛里推荐“压位”，也就是把每9位十进制数打包成一个int，基底BASE=1000000000。这样vector的长度会缩小到原来的九分之一，加法和乘法都快很多。

压位的本质是换一个进制：我们不使用10进制，而是使用10^9进制。这个进制的每一位最大是999999999，两个这样的数相乘再进位也不会超过int范围吗？需要小心。乘法是大数每一位乘以一个普通整数，乘积可能会超过int上限，所以要用long long来存中间结果。例如当前位是999999999，乘以系数200，乘积是199999999800，再加上进位，仍然在long long范围内，完全没问题。

加法进位时，因为两个小于10^9的数相加，最大不超过2×10^9，再加进位也不超过2×10^9+1，还是int范围内，但为了稳妥起见我们也可以用int或long long。下面代码里我用int足够。

4.3 高精度加法与乘法的板子

先看加法。两个大数从低位到高位逐位相加，维护进位。注意两个数的长度可能不一样，短的按0处理。

const int BASE = 1000000000; // 10^9 using BigInt = vector<int>; 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，也就是题目递推中的(k+1)或(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 = vector<int>; 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 的方案数 vector<vector<BigInt>> dp(n + 1, vector<BigInt>(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)，系数 j+1 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 本地测试与自检方法

我建议拿到代码先测几组小数据，跟手算结果对照：

• n=3，k=0，输出1；k=1，输出4；k=2，输出1。
• n=4，k=1，输出11。
• 任何n，如果k=0，输出永远是1。这个可以理解：所有元素都不超过自己的位置，只有严格递增排列123...n一种，所以是1。
• 任何n，如果k=n，输出0。

还有一个更稳的测试：把输出所有k的和，看看是不是n!。比如n=5，欧拉数分布是1,26,66,26,1，总和120=5!。你可以临时在主函数里加一个循环求和，验证高精度加法是否正确。

5.3 复杂度分析

状态数是O(n^2)。每个状态做一次大数乘小整数和一次大数加法，大数位数大约是O(n log n)量级。整体时间复杂度上界可以写成O(n^3 log n)，听起来有点吓人，但n只有200左右时跑起来非常快，本地VSCode一秒都用不了。

空间方面，如果直接用二维vector存所有dp[i][j]，会存下矩阵里的每个高精度数。n=200时，状态数约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，当j=i时为0，所以A(n,n)=0。mul函数开头要判断m==0，直接返回0，否则如果a是空vector会发生奇怪的问题。我把所有大数初始化为{0}，可以避免空vector索引越界。

第四个坑是“高精加法进位的顺序”。压位加法要从低位到高位，vector下标0是低位。如果反过来处理，进位方向全乱。写的时候最好注释清楚，免得过两天自己都看不懂。

6.2 如果题目改成“至少k对”

有些变体问题会问“男高对不少于k”的方案数。这时候不需要重新推导DP，只需要在得到整行欧拉数后做一个后缀和：ans = sum_{j=k}^{n-1} dp[n][j]。因为欧拉数分布的性质，这个后缀和也可以用高精度加法轻松得到。注意如果k为负数（理论上不会），就变成全排列数n!。

如果题目进一步要求输出概率，也就是方案数除以n!，那就更复杂了。因为高精度下无法方便地做浮点除法，通常需要额外实现大数除法，或者改用模意义下的DP。不过在SHOI2009原题里，只要求输出方案数，所以我们不需要处理。

6.3 欧拉数的其他求法，什么时候用

欧拉数除了上面的O(n^2)递推，还有生成函数、整式递推等高级方法。如果n特别大，比如n=10^5，并且答案对质数取模，可以用卷积或多项式求逆在O(n log n)内求出整行欧拉数。但本题要求高精度，而且n不大，O(n^2)高精度递推就是最简单可靠的选择。

另外，如果题目允许Python，直接用Python写会非常轻松，因为Python的int天生支持任意精度，只需要把上面的DP用Python写一遍，代码短一半。但C++选手练习高精度从来不是坏事，毕竟很多题目都得靠这套板子。我个人建议把add和mul当成模板背下来，以后遇到“DP结果巨大”的题直接套。

6.4 一点实战心得

最后说点我自己的体会。这题真正难的其实不是高精度，而是“把配对看成排列”这层转化。我第一次做的时候，卡在“如何维护男生女生同时匹配”的状态上，绕了大半天。后来在纸上画了几组小数据，突然意识到每个男生最终一定只对应一个女生，这不就是排列吗？一旦看出这一点，后面的欧拉数递推就是顺水推舟。

所以遇到计数类DP，不要急着设状态。先把问题数学化，看看能不能用排列、组合、图论这类已知模型来描述。很多时候，模型转化做得好，DP方程就自然浮出水面。P2159这道题虽然老，但知识点非常综合：排序、排列、组合恒等式、动态规划、高精度，全串在了一个“舞会”壳里。把它吃透，比盲目刷十道同类型的题都管用。