RdOIR2 C题解

Subtask 1： 随便打打就完了 估计是 $O(n\log n)$ 级别的，反正咋都能过。 Subtask 2： $f(x)=\sum\limits_{d|x}{a_{\frac{x}{d}}\times\prod\limits_{i=1}^{k_d}{C_{c_{d,i}+m}^{m}}}$ $=\sum\limits_{d|x}{a_{\frac{x}{d}}\times\prod\limits_{i=1}^{k_d}{C_{c_{d,i}+m}^{c_{d,i}}}}$ 最后的那坨显然是插板法的结果，化成在 $c_{d,i}+m+1$ 个 $1$ 中插 $m$ 个板，版不能重合，分成 $m+1$ 段的方案数。 前面的 $m$ 似乎没啥关系，我们把每段 $-1$，即把 $c_{d,i}$ 分成 $m+1$ 段的方案数，每段可以等于 $0$。 考虑再转化一步，是一个长度为 $m+2$ 段的非严格递增序列满足第一个数是 $0$ 且最后一个数是 $c_{d,i}$ 的方案数。 把那个乘积整体考虑，得到是一个长度为 $m+2$ 的序列满足后一个数是前一个数的倍数（可以相等）且第一个数是 $1$ 最后一个数是 $d$ 的方案数。 这似乎是在统计 $a_{\frac{x}{d}}$ 对答案的贡献，发现它是每次都取 当前数的一个因数（一开始当前数是 $x$），取 $m+1$ 次后恰好取到 $\dfrac{x}{d}$ 的方案数。 到这里应该比较明显了，这是一个 Dirichlet 前缀和，做 $m+1$次，就有了 $f$ 所有的取值。 复杂度 $mn\log \log n$。 ~~nlogn的做法与这个我的写法只差一点点 不知道是否在赛时会被暴力过掉~~ 然后你会发现这么写过不了，至少是比较卡。 可以在取模的时候加一个优化，在读入的时候取模，剩下的因为全是加，可以先加，如果大于等于 mod 就减掉。 [代码](https://www.luogu.com.cn/paste/vxucs527)