白给多项式

[题目链接](https://www.luogu.com.cn/problem/CF1731F) $\Theta(\log n)$ 解法。 先说结论，对于 $n>1$： $$F(x)=\sum_{i=1}^n\sum_{j=0}^{i-1}\binom{i-1}{j}(x-1)^j(m-x+1)^{i-j-1}\sum_{k=j+1}^{n-i}\binom{n-i}{k}(m-x)^kx^{n-i-k}$$ 满足 $\deg F(x) = 1$（式中的 $m$ 就是题面中的 $k$）。 **** 首先可以发现，如果最内层和式的 $k$ 每次都从 $0$ 取到 $n-i$，那结果必然是一个常数。考虑将其取值范围改为 $0$ 到 $j$，此结果的度数不大于 $1$，当且仅当 $\deg F(x)\leq 1$： $$G(x)=\sum_{i=1}^n\sum_{j=0}^{i-1}\binom{i-1}{j}(x-1)^j(m-x+1)^{i-j-1}\sum_{k=0}^j\binom{n-i}{k}(m-x)^kx^{n-i-k}$$ 然后我们可以根据 $$\binom{n-i}{k}=[y^{n-i}]\frac{y^k}{(1-y)^{k+1}}$$ 将上式化为 $$\begin{aligned} G(x)&=\sum_{i=1}^n[y^{n-i}]\sum_{j=0}^{i-1}\binom{i-1}{j}(x-1)^j(m-x+1)^{i-j-1}\sum_{k=0}^j \frac{y^k(m-x)^k}{(1-xy)^{k+1}}\\ &= \sum_{i=1}^n[y^{n-i}]\sum_{j=0}^{i-1} \binom{i-1}{j}\frac{(x-1)^j(m-x+1)^{i-j-1}}{1-my}\left( 1-\frac{(m-x)^{j+1}y^{j+1}}{(1-xy)^{j+1}}\right)\end{aligned}$$ 同样我们发现 $G(x)$ 中提取出一部分是常数，就只需要证明此式度数不大于 $1$： $$\sum_{i=1}^n[y^{n-i}] \frac{(m-x)y}{(1-xy)(1-my)}\sum_{j=0}^{i-1}\binom{i-1}{j}\left(\frac{(x-1)(m-x)y}{1-xy}\right)^j(m-x+1)^{i-j+1}$$ 式子中还可以提取出一个 $(m-x)$ 来，那就只需要证明此式度数为零即可： $$ \begin{aligned}& [y^n]\sum_{i=1}^n \frac{y^{i+1}}{(1-xy)(1-my)}\left( \frac{(x-1)(m-x)y}{1-xy}+(m-x+1)\right)^{i-1} \\ &= [y^n]\frac{y^2}{(1-xy)(1-my)}\sum_{i=0}^\infty y^i\left( \frac{(x-1)(m-x)y}{1-xy}+(m-x+1)\right)^i \end{aligned}$$ 把 $i$ 的求和上界调到无穷大是常用技巧，因为提取 $i>n$ 项的系数必然为零。这样就化简为 $$\begin{aligned} & [y^n]\frac{y^2}{(1-xy)(1-my)} \times \frac{1}{1-y\left( \frac{(x-1)(m-x)y}{1-xy}+(m-x+1)\right)} \\ &=[y^n] \frac{y^2}{(1-my)} \times \frac{1}{(1-xy)-y\left((x-1)(m-x)y+(m-x+1)(1-xy) \right)} \\ &= [y^n] \frac{y^2}{(1-my)}\times \frac{1}{(1-y)(1-my)}\end{aligned}$$ 是一个常数，命题得证。 **** 有了这个结论，我们就可以根据 $$F(1)=nm^{n-1}-\frac{1-m^n}{1-m} \ , \ F(m)=0$$ 直接解出 $$F(x)=\frac{1+m^{n-1}(nm-n-m)}{(1-m)^2}(m-x)$$ 答案为 $$\sum_{i=1}^m i F(i)=\frac{1+m^{n-1}(nm-n-m)}{(1-m)^2}\binom{m+1}{3}$$ 时间复杂度 $\Theta(\log n)$。