P9438 题解

对于一次询问，相当于在考虑整数 \(\frac{n}{x}\) 变为 \(1\) 的方案数。进一步的，这相当于给定一个数列 \(c_0\cdots c_k\)，每一次可以减小任意位的任意值，但不能空选，问方案数，这里“空选”指的是不选任何一个数。

先考虑允许空选的时候应该怎么做，令 \(f(x)\) 代表正好走了 \(x\) 步变为 \(0\) 的方案数，允许空选。这个很简单，针对每一位都插板容斥，答案 \(f(x)=\prod_{i=1}^k\limits\binom{c_i+x-1}{x-1}\)。

而我们进一步考虑 \(g(x)\) 为正好走了 \(x\) 步变为 \(0\) 的方案数，不允许空选。这个也只需要针对 \(f\) 进行容斥，枚举空选步数，大力推式子得出 \(g(x)=\sum_{i=0}(-1)^{x-i}\binom{x}{i}f(i)\)。

容易发现，\(Ans=\sum g(i)\)。

\(f\) 暴力，\(g\) NTT 卷一下就行。不会 NTT 的小朋友们就平方复杂度的推出结果，此题一样可以通过。