初赛一

1005

由于 aia_i 递增,故一个内层点最多连向两个相邻外层点。又因为需要黑白染色,所以一个黑点最多只会向外连一个黑点。故构成了森林,根据期望的线性性计算答案即可

1007

二分答案,即转化为二分图匹配问题,显然用Hall定理解决。

设左部为初始蚊子点,右部为 n×mn \times m 个格子

注意到,右部看上去有 n×mn \times m 个点,事实上只存在 2k2^k 种本质不同的,向左部的连边方式,即可以缩成 2k2^k 个点

于是问题又可以转化为,对于左部的每个集合SS,判断右部中所有满足连向左部的点集是 S 的子集的点的数目是否大于SS的点权和

高维前缀和处理即可

1008

i=1ndi[(d,id)=1]d=d=1ndi=1nd[(d,i)=1]=d=1ndi=1ndg(d,i)μ(g)=g=1nμ(g)d=1ngdgndg2 \begin{aligned} &\sum_{i = 1}^{n} \sum_{d | i} [(d, \frac{i}{d}) = 1] d\\ =&\sum_{d = 1}^{n} d \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor} [(d, i) = 1] \\ =&\sum_{d = 1}^{n} d \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor} \sum_{g | (d, i)} \mu(g) \\ =&\sum_{g = 1}^{n} \mu(g) \sum_{d = 1}^{\lfloor \frac{n}{g} \rfloor}dg\lfloor \frac{n}{dg^2} \rfloor \\ \end{aligned}

由于 d>ng2d > \lfloor \frac{n}{g^2} \rfloorndg2=0\lfloor \frac{n}{dg^2} \rfloor = 0,那么dd的枚举上界可以改为 ng2\lfloor \frac{n}{g^2} \rfloor

而当 g>ng > \sqrt n 后,ng2=0\lfloor \frac{n}{g^2} \rfloor = 0,所以gg的枚举上界可以改为 n\sqrt n

=g=1nμ(g)gd=1ng2dndg2=g=1nμ(g)gd=1ng2dng2d \begin{aligned} =&\sum_{g = 1}^{\sqrt n} \mu(g) g\sum_{d = 1}^{\lfloor \frac{n}{g^2} \rfloor}d\lfloor \frac{n}{dg^2} \rfloor \\ =&\sum_{g = 1}^{\sqrt n} \mu(g) g\sum_{d = 1}^{\lfloor \frac{n}{g^2} \rfloor}d\lfloor \frac{\lfloor \frac{n}{g^2} \rfloor}{d} \rfloor \\ \end{aligned}

预处理μ\mu,枚举 gg,后半部分对ng2\lfloor \frac{n}{g^2} \rfloor整除分块即可

总复杂度是 i=1nni2=O(nlnn)\displaystyle \sum_{i=1}^{\sqrt n} \sqrt{\frac{n}{i^2}} = O (\sqrt n \ln{\sqrt n})