F_牛客博客

经典的，我们容斥，此时可以简单理解成将值域划分若干段，每个长度的贡献乘在一起，最后设用了 $k$ 段，则乘以 $k!$

简而言之，设 $G(x)=\frac{x^{m+2}-2x^{m+1}+x}{1-x^{m+1}}$ ，则答案可以描述为 $\sum G(x)^k k!$

设 $H(x)=\sum x^kk!$ ，那么我们只需要计算 $H(G(x))[x^n]$ ，设 $G(x)$ 的复合逆为 $F(x)$

由拓展拉格朗日反演：

$H(G(x))[x^n]=\frac{1}{n}H(x)'\bigg(\frac{x}{F(x)}\bigg)^{n}$

解 $F(x)$ 则只需要考虑如下方程：

$F_0(x)=F(x)-\frac{x^{m+1}F(x)^{m+2}+x^{m}(x-2)F(x)^{m+1}+F(x)-1}{(m+2)x^{m+1}F(x)^{m+1}+(m+1)x^{m}(x-2)F(x)^{m}+F'(x)}$

复杂度 $\mathcal O(n\log n)$ ，不过常数会十分感人就是了。

不知道为什么牛客的题解区似乎不是非常可以显示 Latex 代码。。。下面是无意义复读。

F'(x)=F(x)-\frac{x^{m+1}F(x)^{m+2}+x^{m}(x-2)F(x)^{m+1}+F(x)-1}{(m+2)x^{m+1}F(x)^{m+1}+(m+1)x^{m}(x-2)F(x)^{m}+F'(x)}
F'(x)=F(x)-\frac{x^{m+1}F(x)^{m+2}+x^{m}(x-2)F(x)^{m+1}+F(x)-1}{(m+2)x^{m+1}F(x)^{m+1}+(m+1)x^{m}(x-2)F(x)^{m}+F'(x)}
F'(x)=F(x)-\frac{x^{m+1}F(x)^{m+2}+x^{m}(x-2)F(x)^{m+1}+F(x)-1}{(m+2)x^{m+1}F(x)^{m+1}+(m+1)x^{m}(x-2)F(x)^{m}+F'(x)}
F'(x)=F(x)-\frac{x^{m+1}F(x)^{m+2}+x^{m}(x-2)F(x)^{m+1}+F(x)-1}{(m+2)x^{m+1}F(x)^{m+1}+(m+1)x^{m}(x-2)F(x)^{m}+F'(x)}
F'(x)=F(x)-\frac{x^{m+1}F(x)^{m+2}+x^{m}(x-2)F(x)^{m+1}+F(x)-1}{(m+2)x^{m+1}F(x)^{m+1}+(m+1)x^{m}(x-2)F(x)^{m}+F'(x)}
F'(x)=F(x)-\frac{x^{m+1}F(x)^{m+2}+x^{m}(x-2)F(x)^{m+1}+F(x)-1}{(m+2)x^{m+1}F(x)^{m+1}+(m+1)x^{m}(x-2)F(x)^{m}+F'(x)}
F'(x)=F(x)-\frac{x^{m+1}F(x)^{m+2}+x^{m}(x-2)F(x)^{m+1}+F(x)-1}{(m+2)x^{m+1}F(x)^{m+1}+(m+1)x^{m}(x-2)F(x)^{m}+F'(x)}F'(x)=F(x)-\frac{x^{m+1}F(x)^{m+2}+x^{m}(x-2)F(x)^{m+1}+F(x)-1}{(m+2)x^{m+1}F(x)^{m+1}+(m+1)x^{m}(x-2)F(x)^{m}+F'(x)}
F'(x)=F(x)-\frac{x^{m+1}F(x)^{m+2}+x^{m}(x-2)F(x)^{m+1}+F(x)-1}{(m+2)x^{m+1}F(x)^{m+1}+(m+1)x^{m}(x-2)F(x)^{m}+F'(x)}
F'(x)=F(x)-\frac{x^{m+1}F(x)^{m+2}+x^{m}(x-2)F(x)^{m+1}+F(x)-1}{(m+2)x^{m+1}F(x)^{m+1}+(m+1)x^{m}(x-2)F(x)^{m}+F'(x)}
F'(x)=F(x)-\frac{x^{m+1}F(x)^{m+2}+x^{m}(x-2)F(x)^{m+1}+F(x)-1}{(m+2)x^{m+1}F(x)^{m+1}+(m+1)x^{m}(x-2)F(x)^{m}+F'(x)}
F'(x)=F(x)-\frac{x^{m+1}F(x)^{m+2}+x^{m}(x-2)F(x)^{m+1}+F(x)-1}{(m+2)x^{m+1}F(x)^{m+1}+(m+1)x^{m}(x-2)F(x)^{m}+F'(x)}
F'(x)=F(x)-\frac{x^{m+1}F(x)^{m+2}+x^{m}(x-2)F(x)^{m+1}+F(x)-1}{(m+2)x^{m+1}F(x)^{m+1}+(m+1)x^{m}(x-2)F(x)^{m}+F'(x)}
F'(x)=F(x)-\frac{x^{m+1}F(x)^{m+2}+x^{m}(x-2)F(x)^{m+1}+F(x)-1}{(m+2)x^{m+1}F(x)^{m+1}+(m+1)x^{m}(x-2)F(x)^{m}+F'(x)}F'(x)=F(x)-\frac{x^{m+1}F(x)^{m+2}+x^{m}(x-2)F(x)^{m+1}+F(x)-1}{(m+2)x^{m+1}F(x)^{m+1}+(m+1)x^{m}(x-2)F(x)^{m}+F'(x)}
F'(x)=F(x)-\frac{x^{m+1}F(x)^{m+2}+x^{m}(x-2)F(x)^{m+1}+F(x)-1}{(m+2)x^{m+1}F(x)^{m+1}+(m+1)x^{m}(x-2)F(x)^{m}+F'(x)}
F'(x)=F(x)-\frac{x^{m+1}F(x)^{m+2}+x^{m}(x-2)F(x)^{m+1}+F(x)-1}{(m+2)x^{m+1}F(x)^{m+1}+(m+1)x^{m}(x-2)F(x)^{m}+F'(x)}
F'(x)=F(x)-\frac{x^{m+1}F(x)^{m+2}+x^{m}(x-2)F(x)^{m+1}+F(x)-1}{(m+2)x^{m+1}F(x)^{m+1}+(m+1)x^{m}(x-2)F(x)^{m}+F'(x)}