311

0311测试

T1

限制是序列每个元素至少要大于左边一半的元素。

先考虑怎么算方案数，填值很不好做，考虑先把排名确定后再根据排名去填值。

然后我们需要的信息就是具体填了几个不同的数，然后就是简单的组合数，可以

T2

T3

筛法模板题。

本质上要算的是。

$$\begin{align} Ans&=\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n\gcd(i,j)[k|\gcd(i,j)]\\ &=\sum_{g=1}^ngd(g)\sum_{i=1}^n\sum_{j=1}^n[\gcd(i,j)=g]\\ &=\sum_{g=1}^ngd(g)\sum_{i=1}^{\lfloor\frac{n}{g}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{g}\rfloor}[\gcd(i,j)=1]\\ &=\sum_{g=1}^ngd(g)\sum_{i=1}^{\lfloor\frac{n}{g}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{g}\rfloor}\sum_{k|\gcd(i,j)}\mu(k)\\ &=\sum_{g=1}^ngd(g)\sum_{k=1}^{\lfloor\frac{n}{g}\rfloor}\mu(k)\sum_{i=1}^{\lfloor\frac{n}{gk}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{gk}\rfloor}1\\ &=\sum_{g=1}^ngd(g)\sum_{k=1}^{\lfloor\frac{n}{g}\rfloor}\mu(k)\lfloor\frac{n}{gk}\rfloor^2\\ \end{align}$$

现在已经可以算了，对 $g$ 数论分块，然后对 $k$ 再数论分块，然后杜教筛算几个函数的前缀和，两次数论分块的复杂度为 $O(n^{\frac{5}{6}})$，可以过了。

注意杜教筛的时候所有的前缀和其实都是算过的，所以能杜教筛，换成 min25 这些筛法是不行的。

可以继续推式子，枚举 $gk=T$：

$$\begin{align} Ans&=\sum_{T=1}^n\lfloor\frac{n}{T}\rfloor^2\sum_{g|T}\mu(\frac{T}{k})d(k)k\\ &=\sum_{T=1}^n\lfloor\frac{n}{T}\rfloor^2\sum_{g|T}\mu(\frac{T}{k})(\operatorname{id} * \operatorname{id})(k)\\ &=\sum_{T=1}^n\lfloor\frac{n}{T}\rfloor^2(\mu * \operatorname{id} * \operatorname{id})(k)\\ &=\sum_{T=1}^n\lfloor\frac{n}{T}\rfloor^2(\phi * \operatorname{id})(k)\\ \end{align}$$

$h=\phi * \operatorname{id}$ 是积性函数，可以杜教筛。

具体的，构造 $h 1 = \operatorname{id} \operatorname{id}$。问题变成了算 $\operatorname{id} * \operatorname{id}$ 的前缀和，它就是 $nd(n)$，可以杜教筛，也可以直接数论分块算：

$$\sum_{i=1}^nd(n)n = \sum_{i=1}^ni\sum_{j|i} 1=\sum_{j=1}^n\lfloor\frac{n}{j}\rfloor$$