March Training Contest 3

No Abstract.

T1

Des.

给一个序列每个位置选一个不超过$2^m$的数, 并且每一位不能被这一位指定的数整除, 并且不能和上一位有交.

Sol.

DP的过程就是把上一位的补集的所有子集的方案算进来嘛, FMT.

然后每做一次特殊处理一下, 把倍数的都毙掉, 继续转移.

T2

Des.

$$\begin{align} \sum_{k=a}^{b}\sum_{i}\sum_{j}[lcm(i,j)=k] \end{align}$$

$i,j$交换位置只贡献一次

Sol.

$$A = \frac{F(b) - F(a-1) + (b - a + 1)}{2}$$

Conclusion I

$$\text{Let }g(x) = \sum_{i}\sum_{j}[lcm(i,j)=x], f(x) = \sigma^2(x). \text{Then:}\\ f(x) = \sum_{d|n}g(d).$$

Prove

$f(x)$的定义是遍历每一对可重的约数, 显然这些约数对的最小公倍数一定整除$x$, 并且只有这些约数对的最小公倍数整除$x$.

莫比乌斯反演

$$g(x) = \sum_{d|x}\mu(d)f(\frac{x}{d}) = \sum_{d|x}\mu(d)\sigma^2(\frac{x}{d})$$

Conclusion II

$$g(x) = \sigma(x^2)$$

Prove

先咕着.

Conclusion III

$$g(x) = \sum_{d|x}2^{|\omega|}, \omega = \{p | p \text{ is prime, } p |d\}.$$

并且$2^{|\omega|}$还是$x$的无平方因子的约数个数, 所以有:

$$2^{|\omega|} = \sum_{d|x}{\mu^2(x)}$$

做各种卷积, 得到:

$$g(x) = (\mu^2*\sigma)(x)$$

枚举约数, 就有:

$$\sum_{i=1}^{n}\mu^2(i)\sum_{j=1}^{\lfloor\frac{n}{i}\rfloor}\sigma(j)$$

$\sigma$可以快速分块. $\mu^2$我们可以枚举平方因子群, 一开始有$n$个数, 减去含至少一个平方因子的, 加上两个, 减去三个……

式子就是:

$$\sum_{i=1}^{\sqrt{N}}\mu(i)\lfloor\frac{N}{i^2}\rfloor$$

然后杜教筛就被踩爆了。

T3

Des.

有若干支队伍, 给定出发和返回的时刻. 有规则: 出发时门自动打开, 如果有钥匙可以关上. 返回时要么门开着, 要么有钥匙, 但返回后无论是否有钥匙都可以关门. $n$支队伍只能有$k$把钥匙, 求门的最长关闭时间. 保证所有的$l,r$都不相同.

Sol.

把所有坐标排序, 考察相邻两个坐标, 有四种情况, 讨论一下就可以判断这其中谁必须有钥匙.

对于双方都要有钥匙的, 连一条边, 权值为收益, 只有两点都选时贡献. 最后最多连成若干条链. 做DP即可.