哎跟风发一下。
前边的工作类似，设 \(F_i(x)\) 表示从高到低考虑到了第 \(i\) 位，且第 \(i\) 位向下退 \(x\) 的方案数，其中初值为 \(F_0(x)=1\)，根据转移可以归纳出这是一个 \(i\) 次多项式。然后就有经典的插值做法，可以做到 \(O(n^3)\)，但是不够 strong，考虑不去维护点值，而是维护系数。答案是 \(F_N(1)\)，那么实际上是求 \(F_N(x)\) 的系数。
\[\begin{aligned} F_{n}(x)&=\sum_{y=0}^{kx-1}F_{n-1}(y)\\ \sum_{i=0}^{n}f_{n,i}x^i&=\sum_{i=0}^{n-1}f_{n-1,i}\sum_{y=0}^{kx-1}y^i\\ \sum_{i=0}^{n}f_{n,i}x^i&=\sum_{i=0}^{n-1}f_{n-1,i}\dfrac{1}{i+1}\sum_{j=1}^{i+1}\binom{i+1}{j}B_{i+1-j}{(kx)}^{j}\\ f_{n,i}&=k^{i}\sum_{j=i-1}^{n}f_{n-1,j}\dfrac{1}{j+1}\binom{j+1}{i}B_{j+1-i}\\ f_{n,i}&=k^{i}\sum_{j=i-1}^{n}f_{n-1,j}\dfrac{j!}{i!(j+1-i)!}B_{j+1-i}\\ \end{aligned} \]第三步是用伯努利数展开自然数幂和，后边的 \(f_{n,i}\) 需要满足 \(i\geq 1\)。观察到转移实际上是一个卷积，此时可以做到 \(O(n^2\log n)\)。
考虑这是一个格路计数的形式，设路径为 \((0,0)\to (1,a_1)\to (2,a_2)\to\ldots \to (n,a_n)\)，可以写出贡献：
\[\dfrac{1}{a_n!}\prod_{i=1}^{n}k^{a_i}\dfrac{B_{a_{i-1}+1-a_i}}{(a_{i-1}+1-a_i)!} \]其中需要满足 \(a_i\geq 1,a_{i}\leq a_{i-1}+1\)，可上可下的形式不够优美，改写一下。令 \(b_i=a_{i-1}+1-a_i\)，条件变为 \(b_i\geq 0,\sum_{j\leq i}b_j<i\)，变成了不能碰到 \(y=x\) 且只能往右上走的形式。设 \(m=\sum b_i\)，贡献变为：
\[\dfrac{k^{n(n+1)/2-(n+1)m}}{(n-m)!}\prod_{i=1}^{n}k^{ib_i}\dfrac{B_{b_i}!}{b_i!} \]设 \(G(x)=\prod_{i=0}^{n}B_{i}\dfrac{x^i}{i!}\)，我们希望对于 \(m\in [0,n-1]\) 求出 \([x^m]\prod_{i=1}^{n}G(k^ix)\)……吗？
好像没有满足 \(\sum_{j\leq i}b_j<i\) 的限制。考虑这样一件事：合法等价与路径与 \(y=x\) 无交，那么考虑钦定路径和 \(y=x\) 的交点进行容斥。
交点 \((u,u)\) 和 \((v,v)\) 之间的贡献为 \([x^{v-u}]\prod_{i=u+1}^{v}G(k^{i}x)=k^{u(v-u)}[x^{v-u}]\prod_{i=1}^{v-u}G(k^ix)\)，那么实际上我们需要知道的就只是所有的 \([x^m]\prod_{i=1}^{m}G(k^ix)\)，设其为 \(w_{m}\)，下边考虑如何求出所有 \(w_m\)。
化 \(\prod\) 可以考虑 \(\ln-\exp\) 的方法，设 \(H(x)=\ln(G(x))\)，有：
\[\begin{aligned} \ln(\sum_{i=1}^{n}G(k^ix))&=\sum_{i=1}^{n}\sum_{j=0}^{\infty}h_{j}(xk^i)^j\\ &=\sum_{j=0}^{\infty}h_jx^jk^j\dfrac{1-k^{nj}}{1-k^j}\\ \end{aligned} \]继续设 \(R(x)=\sum_{j=0}^{\infty}h_jx^jk^j\dfrac{1}{1-k^j}\)，那么原式就为 \([x^n]\exp(R(x)-R(k^nx))=[x^n]\exp(R(x))\exp(-R(k^nx))\)。考虑设 \(P(x)=\exp(R(x)),Q(x)=\exp(-R(x))\)，可以写出 \(w_{n}=\sum_{i=0}^{n}Q_{i}P_{n-i}k^{ni}\)，这是一个卷积的形式（\(k^{ni}\) 可以用 bluestein 化掉），那么就可以 \(O(n\log n)\) 求了。
设 \(f_{i}\) 表示走到 \((i,i)\) 的方案数，有 \(f_{i}=-\sum_{j=0}^{i-1}f_jw_{i-j}k^{j(i-j)}\)，这是一个半在线卷积的形式（\(k^{j(i-j)}\) 也可以用 bluestein 化掉），可以整成一个求逆的形式，所以这部分是可以做到 \(O(n\log^2 n)\) 或 \(O(n\log n)\) 的。
还要有统计答案的问题，实际上我们只是需要知道系数和，那么就可以在最后一列添加一列系数全 \(1\) 的列，具体表现就是乘上一个 \(\dfrac{1}{1-x}\) 最后求 \(x^{n+1}\) 的系数。额外设 \(w'_{m}=[x^m]\dfrac{1}{1-x}\sum_{i=1}^{m-1}G(k^ix)\)，用同样的方法可以得到：\(w'_{n}=\sum_{i+j\leq n}Q_iP_{j}k^{(n-1)i}\)，对 \(P(x)\) 的系数做前缀和即可转化为卷积的形式。最终答案即为：\(\sum_{i=0}^{n+1}f_{i}w'_{n+1-i}\)。
至此，我们可以在 \(O(n\log n)\) 的复杂度做出这道经典问题的一个特殊版本。
标签：ix,加强版,dfrac,sum,polylog,exp,加强,prod,log From： https://www.cnblogs.com/tiatto/p/17973556