Educational CodeForces Round 186 T4小记

一道朴素的组合数学题

原题描述

翻译：有 个人决定装饰一棵圣诞树。他们有 盒装饰品，编号从 到 。初始时，第 盒装有 件装饰品。

我们称一个大小为 的排列 （即一个大小为 的数组，其中数字 到 每个恰好出现一次）是公平的，如果可以使用以下过程将所有的装饰品挂到树上

• 人 从盒子 或盒子 中取一件装饰品，并将其挂到树上；
• 人 从盒子 或盒子 中取一件装饰品，并将其挂到树上；
• 依此类推；
• 在人 之后，再由人 继续，该过程循环重复，直到所有装饰品都挂到树上。

在这个过程中，不允许出现以下情况：当轮到时人 需要挂一件装饰品，但盒子 和盒子 都空了。如果无法避免这种情况，则该排列不是公平的。然而，如果人们可以在每一步中选择从哪个盒子取装饰品，从而避免这种情况发生，则该排列是公平的。

你的任务是计算公平排列的数量。由于答案可能很大，请输出其对 998244353 取模的结果。

思路：考虑失败（即排列不公平）的情况，某个时刻，某人 需要取装饰，但 且 。所以很容易想到

• 当一个人 的个人盒子非空时，优先选取自己的盒子，这样不用消耗公共盒子的资源；
• 当一个人 的个人盒子已空时，他必须选取公共盒子的资源。

考虑那些最后可以成功（即排列公平）的情况，其需满足以下条件之一

• 全部选取完成后，所有人选取的数量相同；
• 全部选取完成后，有 人选取了 次，另外的 人选取了 次，且前 次选取都是由选取了 次的人选取的。

怎么这么像平衡树的定义，其实无关

于是我们就很快有了这样的思路：“劫富济贫”，将公共盒子的资源分给所有资源不足 的盒子即可。

易知

若出现比 大的 ，则无法分配，输出 -1 即可。

对于可以分配的情况，则可以将个人盒子分为 类

• 第一类为本身资源就已经是 的，有 个；
• 第二类为本身资源数小于 的，但经过分配后变为 ，有 个；
• 第三类为本身资源数小于 的，但经过分配后变为 ，有 个。

一次遍历很容易求得 ，对于 ，其值应为

可将其归一化为

容易看到前文的 就是 与 的和，。

最后公平排列的数量的含义即为：从非第一类的 个资源中选取 个成为第二类资源，一二类资源将成为一体，需要自排列，第三类资源也需要自排列，记得边乘边模即可，整体复杂度 。

好笑的是我在计算 时漏考虑了整除的情形，导致比赛结束后才发现，喜提 CF 掉分

彩蛋：以下来自 scugqb 用户的部分代码

int n;
cin >> n;
int all = 0;
for (int i = 0; i <= n; i++) {
    cin >> a[i];
    all += a[i];
}
if (all == 0) {
    cout << jc[n] << endl;
    continue;
}
int k = all / n;
int r = all % n;
int ggc = 0; //公共池
int e = 0;
for (int i = 1; i <= n; i++) {
    if (k > a[i]) {
        ggc += (k - a[i]);
    }
    if (a[i] <= k) e++;
}
if (a[0] < ggc) {
    cout << 0 << endl;
    continue;
}
int M = a[0] - ggc;
int ans = 0;
int low = max((int) 0, r - (n - e));
int high = min(r, e);
for (int x = low; x <= high; x++) {
    if (x <= M) {
        ans = (ans + C[e][x] * C[n - e][r - x]) % mod;
    }
}
ans = ans * jc[r] % mod * jc[n - r] % mod;
cout << ans << endl;

他的代码竟然奇迹般的 AC 了！但我们可以看到他使用的是分别从两堆里面进行选取，逻辑上怎么理解呢，让我们一探究竟。

可以看到，他也是先用平摊的做法，思路与我大差不差，只不过他选择向下取整，并且通过维护公共池数量的方法判断是否可以实现公平排列。而后他确定了选取区间，从两类中分别进行挑选再组合，所以为什么会出现这样的差别呢？难道组合数之间存在一些恒等关系吗？

仔细分析可知，平摊后， 的含义为资源数应比平均值多 的盒子数，而 的含义为可通过分配使得资源数可比平均值多 的盒子数，故 恒成立， 恒成立， 为分配前就已经实现资源数比平均值多 的盒子数（注意只能多 ，再多将会无法实现公平排列，前面的 ggc 变量将大于 ），故 的含义应为需通过分配使得资源比平均值多 的额外选取的盒子数，这个数显然不会小于 ，故 恒成立。接着我们来看 的含义，其定义为平摊后多余出的资源，注意这个平摊只对小于均值 的进行增，对于出现 的这种并未回补，故其值为 ，与 是相等的。

也就是说：他的代码中，循环中的条件语句只会执行第一次，且由于 ，故并不存在组合数相乘，与我的算法本质上是一致的。

进一步探究可以发现，此处的 即为上文的 ； 即为上文的 ，所以他的式子化简后即为

其中

可以看到甚至不需要初始化模意义下的组合数与阶乘的递推，最终的式子十分简洁、美观。

代码略。

😏