![[problem.pdf]]

不妨设 $d^k(n)=D(n^k)$ ，那么有

$$d^k(n)=\prod_{p\in pri}k\times cnt_{p}+1$$
易证其为一个积性函数

要求的即为

$$\begin{eqnarray}& & \sum_{i=1}^{n}d^{k}(i)\
&=& \sum_{i=1}^{n} \prod_{p\in pri}(k \times cnt_{p}+1)\
\end{eqnarray}$$

发现对于不同的 $k$ ,后边的形式也是确定的

所以其实就可以拆成关于 $k$ 的多项式即可

T2

考虑分身存在的位置，在时间轴上位置相同的一定是连续的一段

所以考虑变成一个序列分割问题，设 $f_{i}$ 表示是否存在用假人完成了第 $i$ 个任务的情况

考虑决策点 $j$ ，那么必须要满足条件：$j$ 到 $i$ 这段中独立走能够完成，$j$ 到 $i$ 这段能够额外走到

由于 $x$ 坐标之间互不相同，所以事实上一个位置的假人最多只能影响到一次询问

所以我们考虑将整个答案按照假人完成的询问去分割，考虑设 $f_{i,j}$ 表示当前处理到第 $i$ 个询问，且当前位于 $x_i$ ，当前假人位于 $x_j$ 的方案是否存在

考虑转移，将其分为两种可能

  • 这一步由真人来走，从 $f_{i-1,…}$ 去转移
  • 这一步由假人完成，那么从 $f_{i-2,i}$ 去转移

T3

不妨设每种题目的数量为 $c_i$，由于差不超过 1 的限制，首先会将尽可能的将他们铺平，也就是说每一列的数量一定是 $\left\lfloor\frac{c_i}{2}\right\rfloor$ 和 $\left\lceil\frac{c_i}{2}\right\rceil$ 中的一个，且上取整的数量一定为 $c_i \mod S$

![[problem2.pdf]]