Circular Distance 题解

Eraine · 2024-09-30 16:49:00 · 题解

编号：AT_agc068_a
tag：组合数学
难度：\color{red}{2948}

下文中 n 和 L 的含义与原题目相反（不好意思因为个人原因影响大家阅读体验），请注意在本文中 n 指圆环长度，L 指选择的人数。

要求出最大间隔恰好为 i 的方案总数感觉很不可做啊！所以我们考虑最大间隔 \le i 的方案数。

首先特判一下最大间隔 \le\lfloor\frac{n}{2}\rfloor 的方案数必然是 n\choose L。

然后分类讨论。我们计算钦定 0 必须选的方案数，然后将这个方案数乘上权值 \frac{n}{k} 就是 f_i。

我们对 n 的奇偶性进行分类讨论。当 n 为奇数时，以样例 n=13,L=5 为例，不妨假设当前需要求出 f_5。可以得到下面两张图：

第一张图是合法的，而第二张图是不合法的。我们会发现 4 和 11 距离为 6，不合法。

进一步地，我们会注意到 n 奇数合法当且仅当不存在上下两行的元素水平距离相差 \lt n-2i。那我们不妨把这 L+1 个元素（为了方便这里统计首尾的 0）根据水平排序，然后同时枚举一下相邻项出现在上下两行的次数 j，显然 j 为奇数。假设根据水平坐标升序排列为 a_1,a_2,\dots,a_{L+1}。那么一个水平坐标升序排列合法，必须满足以下条件：

• 当 2\nmid(a_{p+1}-a_p) 时，a_{p+1}-a_p\ge n-2i，且满足这样的 p 个数恰为 j。

令 b_p=a_{p+1}-a_p，转换一下即需满足：

• 当 2\nmid b_p 时，b_p\ge n-2i，且满足这样的 i 个数恰为 j。

把满足 2\nmid b_p 的 b_p 全部忽略。剩下的共有 L-j 个偶数元素。发现这又要去枚举这些元素和很不方便，我们将那 j 个奇数元素看做是某个偶数元素加上固定的常数 C，具体地，C=n-2i-2。那么问题转换成两个独立子问题：

• 非零偶数序列 b_1\dots b_L 满足 \sum b_p=n-jC 的方案数。隔板法求出。
• 在 L 个元素中选择 j 个数进行 +C 操作。

两个问题的答案都是组合数，乘起来就是 (i,j) 的贡献，注意到 2L+j(2-2i-2)\le n，即可被统计到的 (i,j) 实际上是 \Theta(n\ln n) 级别。所以就得到一个 \Theta(n\ln n) 解决 n 为奇数的做法。