感觉自己没啥思维，所以做一做 AGC。
E - BBQ Hard
答案即为：
\[\left(\sum_{1 \le i \le n} \sum_{1 \le j \le n} \binom{a_i + a_j +b_i + b_j}{a_i + a_j} - \sum_{1 \le i \le n} \binom{2a_i + 2b_i}{2a_i}\right) \times \frac{1}{2} \]现在的问题就是求出前面那一坨：
\[\begin{aligned} &\sum_{1 \le i \le n} \sum_{1 \le j \le n} \binom{a_i + a_j +b_i + b_j}{a_i + a_j} \\ = \ &\sum_{1 \le i \le n} \sum_{1 \le j \le n} [x^{a_i +a_j}](1+x)^{a_i + a_j +b_i + b_j} \\ = \ & [x^0] \left(\sum_{1 \le i \le n} x^{- a_i} (1+x)^{a_i +b_i}\right)^2 \\ = \ & [x^0] \left(\sum_{i} \left(\sum_{1 \le j \le n} [a_j +b_j = i]x^{- a_j}\right) (1+x)^{a_i +b_i}\right)^2 \\ \end{aligned} \]不难在 \(O(n + V^2)\) 的时间内完成。
总时间复杂度 \(O(n +V^2)\)。
也有组合意义的做法，就是拆成网格图两点之间的路径条数然后 DP，效果是一样的。
标签：le,记录,sum,AGC,right,binom,left From： https://www.cnblogs.com/definieren/p/18608933