CF1957 sol

cmk666 · 2024-04-22 08:06:46 · 个人记录

A

显然全组成正三角形最优，答案为 \displaystyle\sum_i\left\lfloor\dfrac{cnt_i}3\right\rfloor。

B

找到最大的 2^x-1\le k，构造 2^x-1,k-(2^x-1) 和 n-2 个 0 即可，容易证明这样达到了上界。注意特判 n=1。

C

首先 k 步操作中，若 x\ne y，相当于 n\gets n-2，否则 n\gets n-1。

枚举后面的操作中 x\ne y 的步数 i。那么相当于先选出 2i 行列，再将它们两两匹配。枚举第一个未被匹配的匹配了谁，方案数为 2i-1，接着再枚举下一个，方案数为 2i-3……以此类推，则答案为 \displaystyle\binom n{2i}\prod_{j=1}^i(2i-2j+1)，可以递推 O(n) 计算。

D

容易发现 f(x,y)\oplus f(y,z)=f(x,z)\oplus a_y。枚举 a_y，于是问题变成，统计满足 f(x,z) 异或上 a_y 后严格变大的 x,z 个数。

设 a_y 的最高位为 i，那么为了使得异或上 a_y 后变大，f(x,z) 的第 i 位必然是 0。拆成前缀和 s_{x-1}\oplus s_z 后，相当于 s_{x-1} 和 s_z 在第 i 位相同，可以预处理前后缀有多少个第 i 位为 0/1 的 s 来求出。

E

首先有 \displaystyle C(i,j)=\binom ij(j-1)!=\dfrac{i^{\underline j}}j。考虑 (i-j,i]\bmod j 取遍 [0,j)，于是只要找到这里面唯一一个 j 的倍数，除掉 j，然后乘上 (j-1)!\bmod j 即可。发现

于是该贡献可以线性筛出质数后 O(1) 算。

找倍数是比较麻烦的，不妨枚举这个 j 的倍数 k，那么它能贡献到的数为 [k,k+j)，且贡献只和 \dfrac kj\bmod j 有关，调和级数枚举然后差分贡献一下即可。由于有贡献的只有质数和 4，因此时间复杂度可以分析到 O(n\log\log n)。

F1&F2

树上差分，把 cnt_{1\sim10^5} 哈希一下，用主席树维护，每次主席树上二分到第一个哈希不对的位置，到 k 个就退出，复杂度一 \log。