The 2021 ICPC Asia Regionals Online Contest (II) I. Discrete Mathematics

$$ \begin{aligned} & \quad p\cdot [t^m] \sum_{r\ge 1} \frac{\mu(r)}{r}\log \left( 1 + \sum_{k\ge 1} \frac{t^{pr}-1}{t^r -1} p^{k-1} x^{kr} \right) \bmod (t^p-1)\\ &= \sum_{i=0}^{p-1} \omega^{-mi} \sum_{r\ge 1} \frac{\mu(r)}{r}\log \left( 1 + \sum_{k\ge 1} \frac{\omega^{ipr}-1}{\omega^{ir} -1} p^{k-1} x^{kr} \right)\\ &= \sum_{r\ge 1} \frac{\mu(r)}{r}\log \frac 1{1-px^r} + \sum_{i=1}^{p-1} \omega^{-mi} \sum_{p\mid r} \frac{\mu(r)}{r} \log \frac 1{1-px^r}\\ & = \sum_{r\ge 1} \frac{\mu(r)}{r}\log \frac 1{1-px^r} + \left(\sum_{p\mid r} \frac{\mu(r)}{r} \log \frac 1{1-px^r}\right) \cdot \begin{cases} p - 1 & m = 0\\ -1 & m \neq 0 \end{cases} \end{aligned} $$ Which $[x^n]$ can be computed in $\tilde O(\mathsf{factorize}(n) + 2^{\omega(n)})$. 一目了然，不言而喻。