abc240 g
只考虑 \(0 \leq X, Y, Z\) 的情况，显然小于 0 时的路径可以与大于 0 的一一对应。
考虑我们三个方向的增量分别需要 \(X, Y, Z\)，剩下的步数显然是通过走一步该方向又走回来这样子消耗。
记 \(m = (N - X - Y - Z) / 2\)。如果 \(N - X - Y - Z\) 是奇数或者 \(N < X + Y +Z\) 就无解。
枚举三个方向分别多走了几步。
假设我们在 \(X\) 方向多走了 \(i\) 步，那么需要用 \(i\) 步再走回来。
\[\sum_{i = 0}^{m} \sum_{j = 0}^{m - i} \binom {N}{X + i} \binom {N - X - i}{i} \binom{N - X - 2 \times i}{Y + j} \binom{N - x - 2 \times i - Y - j}{j}\binom{N - x - 2 * i - Y - 2 * j}{Z + m - i - j}\binom{N - x - i - Y - j - Z - m}{m - i - j} \]发现这是个多重集组合数，可以给它变成
\[\sum_{i = 0}^{m} \sum_{j = 0}^{m - i} \frac{N!}{(x + i)!i!(Y + j)!j!(Z + m - i - j)!(m - i - j)!} \]把与 \(j\) 无关的提出来
\[\sum_{i = 0}^{m} \frac{N!}{(x + i)!i!}\sum_{j = 0}^{m - i} \frac{1}{(Y + j)!j!(Z + m - i - j)!(m - i - j)!} \]希望后面那一坨带 \(j\) 的式子优美一点，发现 \(Y + j + m - i - j = Y + m - i, Z + m - i - j + j = Z + m - i\)，给他重新凑一下组合系数
\[\sum_{i = 0}^{m} \frac{N!}{(x + i)!i!(Y + m - i)!(Z + m - i)!}\sum_{j = 0}^{m - i} \frac{(Y + m - i)!}{(Y + j)!(m - i - j)!} \frac{(Z + m - i)!}{(Z + m - i - j)!j!} \]\[= \sum_{i = 0}^{m} \frac{N!}{(x + i)!i!(Y + m - i)!(Z + m - i)!}\sum_{j = 0}^{m - i} \binom {Y + m - i}{Y + j} \binom{Z + m - i}{Z + m - i - j} \]对后面那个式子使用范德蒙德卷积
\[\sum_{i = 0}^{m} \frac{N!}{(x + i)!i!(Y + m - i)!(Z + m - i)!}\binom{Y + Z + 2 \times m - 2 \times i}{Y + Z + m - i} \]时间复杂度 \(O(N)\)。
标签：数数,frac,sum,times,几道,binom,式子 From： https://www.cnblogs.com/Svemit/p/18393466