ABC094D Binomial Coefficients

· · 题解

前言：这题是bct tg前集训班的作业题吗，那我做一发。

题解：

首先考虑组合数的性质。

对于一个组合数 C_n^x，其中 x\in [0,n]。

若 2\mid n 则有：C_n^0<C_n^1<C_n^2<\ldots<C_n^{\frac{n}{2}}>C_n^{\frac{n}{2}+1}>C_n^{\frac{n}{2}+2}>\ldots>C_n^n。

否则有 C_n^0<C_n^1<C_n^2<\ldots<C_n^{\lfloor \frac{n}{2}\rfloor}=C_n^{\lceil\frac{n}{2}\rceil}>C_n^{\lceil\frac{n}{2}\rceil+1}>C_n^{\lceil\frac{n}{2}\rceil+2}>\ldots>C_n^n。

先考虑一下部分分。

考虑在 a 中枚举两个数 x，y 且 x\ge y，求 C_x^y 的最大值即可。

但是上面有组合数的性质了，所以：

首先枚举 a 中的一个数 x，然后在 a 数组中二分查找一个最接近 \lfloor \frac{x}{2}\rfloor 和 \lceil \frac{x}{2}\rfloor 的数。容易发现组合数底数是 x 的最大的数就是查找出来的两个数的组合数得到的最大值。

这样需要把 a 数组排序。

这样时间复杂度是 O(n\log n) 的了，时间复杂度足够优秀。

但是这样太难写了（也不难写了），所以继续优化。

发现当组合数底数 x 增大的时候，最优秀的两个组合数顶数 y_1，y_2 也一定会变大。

所以考虑维护三个指针 p_1，p_2，p_3 分别维护组合数底数的下标，小顶数的下标，大顶数的下标。

每一次，把 p_1 从小到大枚举，这样 p_2，p_3 一定不会变小。

容易发现 p_1，p_2，p_3 这三个指针对于 a 数组的 n 个元素都只枚举了 1 次，所以时间复杂度是 O(n) 的。

完了？没有。因为需要把 a 数组排序，所以时间复杂度是 O(n\log n) 的，瓶颈在于排序。

但是写这篇博客的人有强迫症，她认为时间复杂度必须彻底的分析才行。

于是她重新分析了代码的时间复杂度，发现了上面分析的错误。

伪代码大概是这样的：

\bf{Read} \bf{Sort} \textbf{p1, p2, p3} \textbf{p1 in [1,n]} \quad\textbf{find p2, p3} \quad\textbf{calculate }\max(C_{a_p1}^{a_p2},C_{a_p1}^{a_p3}) \textbf{Print Answer}

首先第一行是 O(n) 的没错。

然后第二行 Sort 是 O(n\log n) 的。但是博主想要使用基数排序，时间复杂度是 O(n) 的。

那这样时间复杂度是 O(n) 的啦？

显然不是。

第四行有一个循环。循环中第五行是双指针的板子，已经证明了时间复杂度均摊是 O(n) 的了。

但是第六行呢？

所以求组合数的时间复杂度是 \log 的。

upd：由于没有取模，需要使用高精度，所以不止是 \log 的。

这就让博主陷入了苦恼。

因此这里引入组合数的另一个性质：

证明？

引入一个东西叫做杨辉三角（Pascal Triangle）。

杨辉三角的定义：

通过二项式定理可以得到 a_p^q=C_p^q。

容易发现杨辉三角一行中左边和右边是对称的，所以有 C_n^p=C_n^{n-p}。

又通过了组合数的第一个定义：在序列中间位置左边的数单调递增，右边的数单调递减，所以得证。

那么比较的时候就没有任何的必要把组合数的值算出来了，只需要使用组合数的第二条定理，直接按照和中间点的距离的大小，比较两个同底数的组合数的大小即可。

这样时间复杂度真的成 O(n) 的了。

再upd：

看了一下题解区的做法。Link。发现博主还是tcl。一道水黄被做成了蓝题。

给定一个数组 a。让 a 数组从小到大排序。

当且仅当底数为 a_n 的时候得到的组合数最大。

这又是为什么呢。这我可不知道了qwq

容易发现对于一个比 a_n 小的数 x，那么若 x 为底数的最优秀的顶数是 y，那么 C_{a_n}^y>C_{x}^y。

因此组合数的底数一定为 a_n。顶数直接枚举即可。

但是博主想要让时间复杂度是严格 O(n) 的，发现其实只需要求出 a 数组中最大的数，其他的数扫一遍即可。所以直接做即可。

时间复杂度是严格 O(n) 的。

lbx 好闪，拜谢 lbx！lss 好闪，拜谢 lss！