AtCoder Regular Contest 106

A 106

枚举指数即可。

B Values

要求每个连通块内 \(\sum a=\sum b\)，这样一定可以得到答案。

C Solutions

比较简单的构造。

分 \(m\) 的值进行讨论。

\(m=0\)，直接输出 \([2i-1,2i]\) 即可。
\(m>0\)，在 \(m=0\) 的基础上，增加一个左端点为 \(1\)，右端点很大的区间，可以覆盖掉一些答案，例如得到区间 \([1,6],[2,3],[4,5]\) 此时按右端点排序的答案不变，按左端点排序的答案只会统计到 \([1,6]\)，因此在这个被覆盖的区间中不断增加新的小区间，则总共 \(k\) 个区间可以使按右端点排序的答案达到 \(k-1\)，而按左端点排序的答案始终为 \(1\)，因此 \(n\) 个区间最多达到 \(m=n-2\)，其余的值都不存在构造方案。
\(m<0\)，尝试模仿 \(m>0\) 的构造方法，由于一个区间右端点较小时无法覆盖掉其内部的较小区间，因此 \(m<0\) 实际是不合法的。更进一步地说，按照右端点排序的贪心算法实际上就是正解（感性证明是对于同一位置，其后增加的下一个区间一定右端点越小越优），因此不会存在其余做法得到答案更大的情况。

D Powers *

先简单推式子：

\[\begin{aligned} &\sum_{l=1}^{n-1}\sum_{r=l+1}^n (a_l+a_r)^x\\ =&\sum_{l=1}^{n-1}\sum_{r=l+1}^n \sum_{i=0}^x \dbinom{x}{i} a_l^i a_r^{x-i}\\ =&\sum_{l=1}^{n-1}x!\sum_{i=0}^x \dfrac{a_l^i}{i!} \dfrac{\sum_{r=l+1}^n a_r^{x-i}}{(x-i)!} \end{aligned}\]

这样 NTT 的复杂度是 \(O(nk\log k)\)，无法通过。

考虑把 \(l<r\) 的限制去掉，求：

\[\sum_{l=1}^n\sum_{r=1}^n (a_l+a_r)^x \]

这样可以化成：

\[x!\sum_{i=0}^x \dfrac{\sum_{l=1}^n a_l^i}{i!} \dfrac{\sum_{r=1}^n a_r^{x-i}}{(x-i)!} \]

这样只需要卷一次，最后暴力去掉 \(l=r\) 的情况再除以 \(2\) 即可。

时间复杂度 \(O(nk+k^2)\)。

E Medals *

求满足条件最小转成二分。

判定等价于一个二分图匹配，\(nk\) 个左部点表示每个雇员的每个奖章，\(mid\) 个右部点表示每一天，则要求完美匹配。

根据 Hall 定理，我们需要判断每个左部点集 \(T\) 是否满足 \(|T|\le |N_G(T)|\)。容易发现对应雇员集合 \(S\) 相等的左部点集 \(T\) 的 \(N_G(T)\) 都同，而最大一个满足 \(|T|=k|S|\) 的点集满足条件则代表 \(S\) 对应的全部点集都满足，于是只需要判断 \(2^n\) 个集合。

式子 \(|T|\le |N_G(T)|\) 左侧值为 \(k\operatorname{popcount}(S)\)，右侧值等价于与当天到来的雇员集合与 \(S\) 有交的天数。

求有交自然补集转成求无交，那么就是求集合 \(U\backslash S\) 的所有子集之和，这一部分可以高维前缀和。

注意到每个左部点集连出的右部点数应当不低于 \(mid/2\)，因此当 \(mid\ge 2nk\) 时，一定有 \(|T|\le nk\le |N_G(T)|\)，因此二分区间为 \([nk,2nk]\)，总复杂是 \(O(nk^2+(nk+n2^n)\log (nk))\)。