-
T1
- 可以很容易的发现我们只关心 \(a_1\) 的个数和 \(a_n\) 的个数
- 故我们定义 \(f_{x,y}\) 为 \(\sum a_i = x, a_1 = x-y\) 的局面的概率
- 很容易发现这个东西是具有组合意义的
- 我们考虑 1 后面有 \(x - 1\) 个人，其中 \(n - 1\) 个是舞者，故总方案数为 \(C_{x-1}^{n-1} \cdot (x - n)!\)
- 我们继续考虑 2 的后面有 \(y - 1\) 个人，其中有 \(n - 2\)个是舞者，故合法方案数为 \(C_{y-1}^{n-2} \cdot (x-n)!\)
- 所以 \(f_{x, y} = \frac{C_{y-1}^{n-2}}{C_{x-1}^{n-2}}\)
- 所以最终答案为 \(\sum_{x=n+1}^{n+m} \sum_{y=1}^{x} f_{x,y} \cdot \max(x-2y,0) = \sum_{x=n+1}^{n+m} \cdot \frac{1}{C_{x-1}^{n-1}} \sum_{y=1}^{\frac{x}{2}} C_{y-1}^{n-2} \cdot (x-2y)\)
- 考虑统计 \(y\) 的和 \(s\)，在 \(s\) 数组上打标记来求出答案即可
