思路
看题目递归应该可以解决，长度每多1。动态转移方程：(注意这里的n代表线段长度而非点数量，即原题目中的n-1) 
f(n,k)=1×f(n-1,k-1)+2×f(n-2,k-1)+...+(n-k+1)×f(k-1,k-1) 
但是这样的话会导致时间复杂度变成 O(n^3)，所以我们需要一个最多 O(logn) 办法来求出当前的值。对比 
f(n-1,k)=1×f(n-2,k-1)+2×f(n-3,k-1)+...+(n-k)×f(k-1,k-1) 
我们可以发现 f(n,k)=f(n-1,k)+sum(n-1,k-1) 。所以我们可以每次计算 f(n,k) 的同时累加求出 sum(n-1,k-1)，这样就能在 O(1) 的复杂度内求出 f(n,k)。 
碎碎念
这本来可能应该是个数学题，被我做成了模拟题 😂 不过速度还可以，就这样把。 
代码
class Solution {
 ...