题目链接 \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)。