主要思路
也是比较巧妙的一个转换思想。
我们考虑列式:
\[ \sum_{i = 1}^n \sum_{j = i + 1}^n {a_i + b_i + a_j + b_j \choose a_i + b_i} \]
直接去算或者是按贡献计算都不行,我们考虑转换成这样:
\[ \frac{ \sum_{i = 1}^n \sum_{j = 1}^n {a_i + b_i + a_j + b_j \choose a_i + b_i} – \sum_{i = 1}^n {2(a_i + b_i) \choose a_i + b_i} }{2} \]
前面那个部分我们可以把点\((-a_i, -b_i)\)放在平面上,然后算一个路径计数的 DP 即可(因为平面大小比较小)。前半部分就是所有第三象限的点走到\((x_i, y_i)\)的路径总数,后半部分直接暴力算即可。