command_block 神仙在这篇文章中 $\mathbf {Cycle}$ 构造的部分提到了式子 $\ln\Big(\dfrac1{1-A(x^d)}\Big)$，在 $\bmod x^n$ 的意义下是只有 $O(n/d)$ 项是非零的，因此在关于 $d$ 求和时可以暴力累加。

但是我个人不太理解为何其只有 $O(n/d)$ 项非零。

或者这只是 cmd 大佬的笔误，因为他在推式子转化到这一步之前就不小心多留了一个 $\sum$。

非常感谢！

附，要求的式子的推导如下：

$$\begin{aligned}\mathsf{CYC}(x)&=\sum\limits_k\mathsf{CYC}_k(x)\\&=\sum\limits_k\dfrac1k\sum\limits_{d|k}\varphi(d)A(x^d)^{k/d}\\&=\sum\limits_d\varphi(d)\sum\limits_k\dfrac1{dk}A(x^d)^{k}\\&=\sum\limits_d\dfrac{\varphi(d)}d\ln\Big(\dfrac1{1-A(x^d)}\Big)&\end{aligned}$$

这个式子似乎因为太长所以会被当作代码然后拒绝发帖