组合意义太吃操作了，还是得我代数推导牛。
题意：给出若干个已有元素 \(a_i\)，要求加入一些 \([1,n]\) 内的数且不能和 \(a\) 中已有的相同，使得长度为 \(m\)。定义 \(f(a) = \prod\limits_{i=1}^{m-1} (a_{i+1}-a_i)\)，求所有生成的 \(a\) 的 \(f\) 之和。
做法：
首先注意到两段之间的是独立的，同时总和是 \(O(n)\) 的，所以直接考虑把所有段的生成函数弄出来分治乘就可以做到 \(O(n\log ^2n)\)，现在的问题是每段之间。
假设长度为 \(l\)，分成 \(k\) 段，那么直接写出来生成函数：
\[[x^l]F_k(x) = [x^l] G(x)^{k}
\]
这里 \(F_k(x)\) 是划分成 \(k\) 段的生成函数，\(G(x) = \sum\limits_{i=1} ix^i\)。
化简 \(G\)，变成若干个 \(\frac{x^k}{1-x}\)，算出来最终是 \(\frac{x}{(1-x)^2}\)。
那么带入回原柿，可以得到 \([x^l]F_k(x) = [x^{k-l}]\frac{1}{(1-x)^{2l}}\)。
右边这个柿子我们把这个分式再还原成 \((1+x+x^2\cdots)\)，发现这个东西就等于我有 \(k-l\) 个球放入 \(2l\) 个有区分盒子，直接插板得到方案为 \(\binom{k+l-1}{2l-1}\)，直接 \(O(1)\) 计算即可。
注意到两端的段其实会少一个乘积，但是也很容易，就是我把一个 \(G\) 换成 \(\frac1{1-x}\)，次数少 \(1\) 而已，方案为 \(\binom{k+l-2}{2l-2}\)。如果没有已有元素，即两端都缺，那就再减一即可。