2022/04/11 做题记录

bzoj 4894

矩阵树定理模版。

code: /code/2022.4.11/bz4894.cpp

诗人小G

二分栈维护决策单调性，实际上就是对于栈内的每个元素维护最优决策点是它的区间，加入新点的时候二分判断分段即可。

code: /code/2022.4.11/P1912.cpp

[SDOI2014]数表

$$n \le m$$

$$\begin{aligned} \sum_{i=1}^n \sum_{j=1}^m \sigma_1(gcd(i,j)) &=\sum_{d=1}^n \sigma_1{(d)} \sum_{i=1}^{\lfloor \frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor \frac{m}{d}\rfloor}[gcd(i,j)==1] \\ &=\sum_{d=1}^n \sigma_1{(d)} \sum_{k=1}^{\lfloor \frac{n}{d}\rfloor}\mu(k)\lfloor\frac{n}{kd}\rfloor\lfloor\frac{m}{kd}\rfloor T=kd \\ &=\sum_{T=1}^n\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum_{d|T}\sigma_1(d)\mu(\frac{T}{k}) \end{aligned}$$

而那个不大于 a 的限制实际上就是 $d \le a$，因为有贡献的 (d,T) 对只有 nlogn 级别组，可以暴力加，于是离线下来用树状数组维护区间和就行。

code: /code/2022.4.11/P3312.cpp