YZOJ P3782 [校内训练20180619]组合数问题

时间限制：1000MS 内存限制：524288KB

难度：\(6.5\) 出题人：zzx

• 题目描述

• 输入格式

第一行一个正整数 \(n\) 表示数对个数。

接下来 \(n\) 行，第 \(i\) 行两个正整数 \(a_i, b_i\)，表示一个数对 \((a_i, b_i)\) 。

• 输出格式

一行一个整数，表示所求式子的值。

• 样例输入

• 样例输出

• 样例说明

• 数据规模与约定

保证 \(2 \leq n \leq 200,000\) ， \(1 \leq b_i \leq a_i \leq 2000\) 。

 

 

 

---

 

 

 

首先可以得到 \(\sum\limits_{i = 1}^n {\sum\limits_{j = i + 1}^n {\mbox{C}_{{a_i} + {a_j}}^{{b_i} + {b_j}} = \frac{1}{2}\left( {\sum\limits_{i = 1}^n {\sum\limits_{j = 1}^n {\mbox{C}_{{a_i} + {a_j}}^{{b_i} + {b_j}}} } – \sum\limits_{i = 1}^n {\mbox{C}_{2{a_i}}^{2{b_i}}} } \right)} } \) 。

只需要快速求出 \(\sum\limits_{i = 1}^n {\sum\limits_{j = 1}^n {\mbox{C}_{{a_i} + {a_j}}^{{b_i} + {b_j}}} } \) 。

发现 \(\left( {\begin{array}{*{20}{c}} {0,}&0 \end{array}} \right) – \left( {\begin{array}{*{20}{c}} {n,}&m \end{array}} \right) = \mbox{C}_{n + m}^m\) （注：\(\left( {\begin{array}{*{20}{c}} {0,}&0 \end{array}} \right) – \left( {\begin{array}{*{20}{c}} {n,}&m \end{array}} \right)\) 为从 \(\left( {\begin{array}{*{20}{c}} {0,}&0 \end{array}} \right)\) 至 \(\left( {\begin{array}{*{20}{c}} {n,}&m \end{array}} \right)\) 向上或向右走的路径总条数），因为总共走了 \(n+m\) 个单位长度，其中分别 \(n\) 个单位长度向右走且 \(m\) 个单位长度向上走（\(\mbox{C}_{n+m}^m=\mbox{C}_{n+m}^n\)）。

所以 \(\begin{array}{c} \sum\limits_{i = 1}^n {\sum\limits_{j = 1}^n {\mbox{C}_{{a_i} + {a_j}}^{{b_i} + {b_j}}} } = \left( {\begin{array}{*{20}{c}} {0,}&0 \end{array}} \right) – \left( {\begin{array}{*{20}{c}} {{a_i} + {a_j} – {b_i} – {b_j},}&{{b_i} + {b_j}} \end{array}} \right)\\ = \left( {\begin{array}{*{20}{c}} { – {a_j} + {b_j},}&{ – {b_j}} \end{array}} \right) ~- \left( {\begin{array}{*{20}{c}} {{a_i} – {b_i},}&{{b_i}} \end{array}} \right) \end{array}\) 。

即求所有 \(\left( {\begin{array}{*{20}{c}} { – {a_j} + {b_j},}&{ – {b_j}} \end{array}} \right)\) 至所有 \(\left( {\begin{array}{*{20}{c}} {{a_i} – {b_i},}&{{b_i}} \end{array}} \right)\) 的路径总条数，因为左边右边分别只与 \(i, j\) 有关，所以简单DP即可。

设 \(f_{i, j}\) 为从右上角所有出发点向左下方走到 \((i, j)\) 时的路径总条数。显然，当前 \(\left( {\begin{array}{*{20}{c}} {i,}&{j} \end{array}} \right)\) 等于某个 \(\left( {\begin{array}{*{20}{c}} {{a_k} – {b_k},}&{{b_k}} \end{array}} \right)\) 时，那么路径条数要 \(+1\) ，否则不用，即 \(f_{i, j}=f_{i+1, j}+f_{i, j+1}+mpos\left( {\begin{array}{*{20}{c}} {i,}&{j} \end{array}} \right)\) ， \(mpos\left( {\begin{array}{*{20}{c}} {x,}&{y} \end{array}} \right)\) 表示有几个 \(\left( {\begin{array}{*{20}{c}} {{a_k} – {b_k},}&{{b_k}} \end{array}} \right)\) 等于 \(\left( {\begin{array}{*{20}{c}} {x,}&{y} \end{array}} \right)\) （相当于DP的初始值）。当遇到 \(\left( {\begin{array}{*{20}{c}} { – {a_k} + {b_k},}&{ – {b_k}} \end{array}} \right)\) 时直接贡献答案即可。

最后别忘了减去 \({\sum\limits_{i = 1}^n {\mbox{C}_{2{a_i}}^{2{b_i}}} }\) ，除以 \(2\) 其实并不需要逆元。

因为坐标有的为负，记得数组下标整体偏移。