联合省选 2020 题解

先更点口胡题解。

Day1T1

记(pre_{1/2},suf_{1/2})分别表示两种属性的战士的能量前/后缀和，找到最大的(i)满足(pre_{1,i} le suf_{2,i})，也即(pre_{1,i} +pre_{2,i} le sum_2)。

只需要维护支持单点修改和二分的数据结构即可。树状数组是一种可行的选择。

Day1T2

把普通多项式多项式转化成组合数多项式的形式，即(f(k)=sum_{i=0}^mb_iinom{k}{i})。

于是

[sum_{k=0}^nf(k) imes x^k imes inom{n}{k}=sum_{k=0}^nsum_{i=0}^{min(m,k)}b_iinom{k}{i}x^kinom{n}{k}\=sum_{i=0}^mb_iinom{n}{i}sum_{k=i}^{n}x^kinom{n-i}{k-i}\=sum_{i=0}^mb_iinom{n}{i}x^{i}(x+1)^{n-i} ]

计算({b_i})的过程中不需要使用到除(1)以外的数的逆元，因此对模数没有要求。

Day1T3

根据拟阵那套理论，限定礼品集合(A)和(B)为“最小”和“最大”的等价条件是：对于任意(A)中元素(x)和非(A)中元素(y)，若(Acup{y}setminus{x})是一个基，那么(val_y ge val_x)；集合(B)同理。

此时问题相当于给出若干偏序关系和调整权值的代价函数，要求最小化调整代价。

由于代价函数是凸的，可以运用保序回归那套理论，对所有礼品的权值做整体二分，每次用网络流求一个最小权闭合子图作为权值划分的依据。

Day2T1

状压即可。

Day2T2

只需要实现一个数据结构维护一个无序数集，支持全体数字加一、快速合并、查询所有数异或和。把二进制位反过来建( ext{01-Trie})即可。

Day2T3

求图中所有生成树边权和只需要令每条边边权为(1+w_ix)后在模(x^2)下做普通矩阵树即可，时间复杂度(O(n^3))。

加入了(gcd)一项后套路地进行一次莫比乌斯反演，可以发现答案为(sum_dvarphi(d) imes [mbox{所有边都是}dmbox{的倍数的生成树的边权和}])，看上去需要做(max{w_i})次求行列式，但考虑到参与构成此部分的图中边的总数不超过(m imes sigma_0(w_i))，而一张少于(n-1)条边的图中一定不包含生成树，故求行列式的次数其实只有(O(frac{m imes sigma_0(w_i)}{n-1}))次，总复杂度可以估计为(O(n^4sigma_0(w_i)))。

---

代码等loj上传了数据且有时间了再写。

咕咕咕。