伯努利数的一个应用

给定 \(n,k\)，求 \([x^{k^n}]\prod_{i=0}^{n-1}\frac{x^{k^i}}{1-x^{k^i}}\)，对 \(998244353\) 取模，\(n,k\leqslant 2\times 10^5\)。

直接使用普通多项式和下降幂多项式转化的 \(\text{trick}\) 是容易做到 \(O(n^2\log n)\) 的，但不能做到更优，考虑使用伯努利数技巧。

原问题的生成函数可以写作递推式 \(F_{i}(x)=\sum_{y=0}^{kx-1}F_{i-1}(y)\)，由于是 \(k\) 自然数幂和，刚好可以施加伯努利数技巧，令生成函数的系数为 \(dp_{i,j}\)，有 \(F_{i}(x)=\sum_{j=0}^{n}dp_{i-1,j}\sum_{t=0}^{j}\frac{\binom{j+1}{t}}{t+1}B_{t}(kx)^{j-t+1}，\)则有 \(dp_{i,j}=\sum_{t=j-1}^{n}dp_{i-1,j}\frac{1}{j+1}\binom{j+1}{j+1-t}B_{j+1-t}k^t\)(要求 \(i>0\) 时 \(j>0\))，将其转移的每一步写成序列 \(a\) 后贡献即为 \(\frac{1}{a_{n}!}\prod_{i=1}^{n}k^{a_{i}}B_{a_{i-1}-a_{i}+1}\frac{1}{(a_{i-1}-a_{i}+1)!}\)，令 \(d_{i}=a_{i-1}-a_{i}+1\)，令前缀和 \(s_{i}=\sum_{j=1}^{i}d_{j}\)，则贡献为 \(\frac{k^{\frac{n(n+1)}{2}}}{k^{(n+1)s_{n}}(n-s_{n})!}\prod_{i=1}^{n}k^{id_{i}}\frac{B_{d_{i}}}{d_{i}!}\)，要求对于 \(i>0\) 有 \(a_{i}=i-s_{i}>0\)，即 \(s_{i}<i\)。

现在可以将原问题看作一个格路问题，求 \((0,0)\) 走到 \((n,s_{n})\)，每次只能往上与往右走，要求时刻在 \(y=x\) 这条线的下方(除了在 \(x=0\) 处均不能触碰这条线)，记在每一个 \(x=i\) 的位置向上走的长度为 \(d_{i}\)，则贡献为 \(k^{id_{i}}\frac{B_{d_{i}}}{d_{i}!}\)，最终将获得 \(W_{s_{n}}\) 的额外贡献(\(W_{i}=\frac{k^{\frac{n(n+1)}{2}}}{k^{(n+1)i}(n-i)!}\))，求所有方案贡献积的和。由于每一次到达线的上方之后都会从线出来，这是因为 \((n,s_{n})\) 在线下方，所以最后一个不合法的位置一定刚好在线上，可以借此进行容斥，令 \(f_{i}\) 表示无限制从 \((0,0)\) 走到 \((i,i)\) 的贡献和，\(g_{i}\) 表示 \((n-i,n-i)\) 走到 \((n,s_{n})\) 的贡献和(但此时我们将 \(k^{jd_{j}}\) 的贡献改写为 \(k^{(j-(n-i))d_{j}}\)，而且由于 \(s_{n}\) 可能不等于 \(n\)，在直接施加容斥的过程中往往高度 \(=\) 宽度，所以此时给贡献额外除上一个 \(k^{(n-i)(n-s_{n})}\))，这样就刚好可以抵消了。于是有 \(DP_{i}=g_{i}-\sum_{j=1}^{i}f_{j}DP_{i-j}k^{j(i-j)}\)，如果求出了 \(F\) 和 \(G\)，使用 \(\text{CZT}\) 变换后求个逆就可以了。

考虑 \(F\) 如何求解，令伯努利数的 \(\text{EGF}\) 为 \(F\)(其实就是 \(\frac{x}{e^x-1}\))，则 \(f_{i}=[x^i]\prod_{j=1}^{i}F(k^jx)\)，使用 \(\text{ln,exp}\) 大法后令 \(K=ln F\)，即为求 \([x^i]e^{\sum_{j=1}^{i}K(k^jx)}\)，注意到上面的部分是可以等比数列求和的，即 \([x^i]e^{\sum_{j=1}^{i}\sum_{t=1}^{n}K_{t}k^{jt}x^t}=[x^i]e^{\sum_{t=1}^{n}K_{t}\frac{k^{t(i+1)}-k^{t}}{k^{t}-1}x^t}\)，令 \(R=\sum_{j=1}^{n}\frac{k_{j}}{k^j-1}x^i\)，则相当于求 \([x^i]e^{R(k^{i+1}x)-R(kx)}\)，令 \(Z=e^R，C=\frac{1}{e^R}\)，则求 \([x^i]Z(k^{i+1})C(kx)\) 即可，将其展开后即为求 \(\sum_{j=0}^{i}z_{j}c_{i-j}k^{ij+i}=k^i\sum_{j=0}^{i}z_{j}k^{j^2}c_{i-j}k^{(i-j)j}\)，\(\text{CZT}\) 变换后直接卷积即可。

考虑 \(G\) 如何求解，实际上 \(g_{i}=[x^i]\prod_{j=1}^{i}F(k^jx)(\sum_{j=0}^{n}W_{n-j}\frac{1}{k^{(n-i)j}x^j})\)，可以将其写为 \([x^i]\prod_{j=1}^{i}F(k^jx)(\sum_{j=0}^{n}W_{n-j}\frac{(k^{i+1}x)^j}{k^{(n+1)j}})\)，令 \(T=\sum_{j=0}^{n}\frac{W_{n-j}}{k^{(n+1)j}}x^j\)，则相当于求 \([x^i]\prod_{j=1}^{i}F(k^jx)T(k^{i+1}x)\)，令 \(U=ln T\)，则可写为 \([x^i]e^{R(k^{i+1}x)-R(kx)+U(k^{i+1}x)}\)，令 \(S=R+U\)，\(O=e^{S}\)，则相当于求 \([x^i]O(k^{i+1})C(kx)\)，按前面的方式\(\text{CZT}\) 变换后直接卷积即可。

综上可以做到 \(O(n\log n)\)。