题解 | #小A弹吉他#

题目简略描述：给定正整数 $m(1<=m<=10^{18})$ ，长为 $n$ 的正整数数列 $\{a_n\}$ 满足限制 $\displaystyle\sum_{i=1}^n a_i=m$ ，记 $t_i$ 为 $\{a_n\}$ 中 $i$ 的个数，求 $\max_{n,a_n}\mathrm{mex}(t_1,t_2,\cdots,t_{114^{514}})$

解答：记 $T:=\{t_1,t_2,\cdots,t_{114^{514}}\}$ ，利用集合的无序性，有如下引理

引理1：任意 $k:=\mathrm{mex}~T$ 的 $\{t_n\}$ ，都能找到一个（除去0之后）单调递减的 $\{t'_n\}$ 同样有 $\mathrm{mex}~T'=k$ .

$m=\sum_{i=1}^na_i=\sum_{i=1}^{114^{514}}i\times t_i \\$

不妨设 $\{a_n\}$ 单调递增，由于 $i$ 单调递增，由排序不等式，上式 $RHS\ge \text{逆序和}=\sum i\times t'_i=:s$ ，其中 $t'_i$ 单调递减.此时只改变了 $t_i$ 的顺序，换言之， $T$ 不变( $T'=T$ )，因此仍然保持 $mex~T=k$ ，但是求和比原来小了 $m-s$ ，由于 $t'_n$ 单调递减且 $k\ge1\in T$ ，有 $t'_{a_n}=1$ ，那么将多出的 $m-s$ 加到最大值 $a_n$ 上即可得到一个同样符合求和为 $m$ 的 $\{a_n'\}$ ，此时对应的 $t_n''$ 满足去0后单调递减，或者说去掉索引为 $a_n+m-s$ 的 $t$ 后单调递减

以上引理表明，我们总能认为 $t_n$ 是单调递减的，因为其他情况都可以转换到此且mex不变.最优解的 $t_n$ 也是如此。并且，由于我们排序后只改变了最大元素 $a_n$ ，因此 $\{t_n\}$ 是 $\{*,*,\cdots,*,0,0,*,0,0,0,\cdots\}$ 或者 $\{*,*,\cdots,*,0,0\cdots\}$ 的形状

我们考虑 $\mathrm{mex}~T=k$ ,这等价于 $\{0,1,\cdots,k-1\}\subseteq T$ 且 $k\notin T$ 。我们发现 $T$ 中大于 $k$ 的元素都是没用上的（如果有的话）。如果有大于 $k$ 的元素，由于去0后单调递减，那么有 $t_1>k$ ，将 $1$ 数量减少到 $k$ ，并类似的将多的 $t_1-k$ 加到最大元素 $a_n$ 上，于是得到 $\mathrm{mex} ~T'=k+1$ 的构造，再利用引理做排序，如果 $T''$ 还有大于 $K$ 的元素，重复上述过程。

最终我们得到 $\{t_n\}$ 中没有大于 $k$ 的元素，换言之， $\forall t\in T,t\in\{0,1,\cdots,k-1\}$ ，也即 $T=\{0,1,\cdots,k-1\}$ 。而由于 $\{t_n\}$ 单调递减，于是可以断定 $t_i=k-i$ ，其中 $i=1,2,\cdots,k-2$ ，而第 $k-1$ 个元素为 $t_{a_n}=1$ ，且 $a_n\ge n=k-1$ .因此，我们对 $m$ 的RHS求和得到

$\begin{align*} m=&a_n+\sum_{i=1}^{k-2}i\times(k-i)\\ =&a_n+k\sum i-\sum i^2\\ =&a_n+\frac{k(k-1)(k-2)}{2}-\frac{(k-2)(k-1)(2k-3)}{6}\\ =&a_n+\dfrac{(k-1)(k-2)(k+3)}{6} \end{align*} \\$ 并且 $a_{k-1}\ge k-1$ .基于此基本就可以做二分法了，对 $k$ 在值域上二分，判断 $m-\dfrac{(k-1)(k-2)(k+3)}{6}$ 得到的 $a_{k-1}$ 是否大于等于 $k-1$ ，符合就表明此时的k是一个可行解。

（这里能二分的原因是上面构造保证了小于最优解的构造都存在；或者说二分判断条件是单调的）

提供一个二分的代码：

int main() {
    int t;
    cin >> t;
    while (t--) {
        long long m;
        cin >> m;
        unsigned long long ans = 0;
        long long l = 1, r = 2e6;
        long long mid = (l + r) / 2;
        while (l +1< r) {
            mid = (l + r) / 2;
            long long a = m - (mid - 1) * (mid - 2) * (mid + 3) / 6;
            if (a >= mid - 1) {
                ans = mid;
                l = mid;
            } else r = mid;
        }
        cout << ans << endl;
    }
}

其中有需要注意的一些点，一个显然的是a有负值，不能用unsigned；另外一个比较关键的是r的估计，由于 $m<10^{18}$ ，从上面的计算可以知道，显然 $k$ 是在1e6量级的，但是如果直接r=1e6过不了。当然可以调整出r=2e6可以过，不过我们也可以做一个更好的估计然后不使用二分，直接遍历：

$a_{k-1}\ge k-1$ ,我们可以得到 $k$ 的一个估计：

\begin{align*} m\ge & k-1+\dfrac{(k-1)(k-2)(k+3)}{6}\\ =&\frac{k(k-1)(k-5)}{6}\\ \ge &\frac{(k-5)^3}{6} \end{align*} \\

于是 $k\le \sqrt[3]{6m}+5$ 。有了这个估计就可以直接遍历

int main() {
    int t;
    cin >> t;
    while(t--){
    long long m;
    cin >> m;
    long long k=cbrt(6*m)+5;
    while(true){
        long long a = m - (k-1)*(k-2)*(k+3)/6;
        if(a>=k-1) break;
        k--;
    }
    cout << k << endl;
    }
}

当然，如果注意到 $a_{k-1}$ 上界，还能做到 $O(1)$ 的算法， $a_{k-1}$ 如果足够大，可以分配给1~k-1使得其都多一个，并且自己还能保留大于等于 $k$ 的数量，那么就得到了 $\mathrm{mex}~T=k+1$ 的构造。因此，最优的情况应该要求 $a_{k-1}\le \sum_{i=1}^k i=\frac{k(k+1)}{2}\\$ 于是就有

\begin{align*} m\le & \frac{k(k+1)}{2}+\dfrac{(k-1)(k-2)(k+3)}{6}\\ =&1+\frac{k(k-1)(k+4)}{6}\\ <&1+\frac{(k+4)^3}{6} \end{align*} \\

于是 $k> \sqrt[3]{6(m-1)}-4$ ，综合得到 $k\in(\sqrt[3]{6(m-1)}-4,\sqrt[3]{6m}+5]$ ，可以计算m在R上区间长度值域在 $(9,11.88]$ 之间，因此可以做到11次判断就得到答案（比二分的 $\log_2(2\times10^6)=20.93$ 略少一些并且不用管 $m$ 的大小）

将先前二分的l,r改为l = cbrt(6*(m-1))-3, r = cbrt(6*m)+6即可。

此外，顺带一提，手动测试了一下，l = cbrt(6*(m-1))-1, r = cbrt(6*m)+2也能AC本题，区间长度减少了6，只是不确定是不是严格的上下界，可能是数据比较弱（？）