模拟赛题。
首先考虑答案是什么。
设三个人手里的分别为 \(n_1,n_2,n_3\)。
\(n_1\) 是一定要取完的，\(n_2,n_3\) 是一定取不完的，最暴力的思路就是枚举 \(n_2\),\(n_3\) 各取了几个，得到答案是 \(\sum_{i=0}^{n_2-1}\sum_{j=0}^{n_3-1} 3^{n_2+n_3-i-j} \binom{i+j+n_1-1}{i,j,n_1-1}\)，带 \(3\) 的那一项是后面可以随便选，组合数是插板。
然后发现这个式子跟 \(i+j\) 有很大关系，转过头去枚举 \(i+j\)，变成 \(\sum_{i=0}^{n_2+n_3-2} 3^{n_2+n_3-i}\binom{i+n_1-1}{n_1-1}\sum_{j \in [0,n_2], i-j \in [0,n_3]}\binom{i}{j}\)
难点在于最后一个式子，是一行组合数部分求和。
考场上直接把组合数拆开然后暴力 MTT，跑起来很快。
当然有别的方法，考虑从 \(i-1\) 递推出 \(i\)，发现仅仅只需要两项修改。
submission
