CF div2 1008 F（组合数学+推公式）

猿柒

1个月前发布

1008 F

题意先省略，直接看重点：

计算：

\[\sum_{i=0}^{N_{0}}\sum_{j=0}^{N_{1}}(C_{N_{0}}^{i}\times C_{N_{1}}^{j} \times (i – j)^{2}) \]

可以先把平方拆开：

\[\sum_{i=0}^{N_{0}}\sum_{j=0}^{N_{1}}(C_{N_{0}}^{i}\times C_{N_{1}}^{j} \times (i^{2} + j^{2} – 2 \times i \times j)) \]

再裂项：

\[\sum_{i=0}^{N_{0}}\sum_{j=0}^{N_{1}}(C_{N_{0}}^{i}\times C_{N_{1}}^{j} \times i^{2}) + \sum_{i=0}^{N_{0}}\sum_{j=0}^{N_{1}}(C_{N_{0}}^{i}\times C_{N_{1}}^{j} \times j^{2}) – 2 \times \sum_{i=0}^{N_{0}}\sum_{j=0}^{N_{1}}(C_{N_{0}}^{i}\times C_{N_{1}}^{j} \times i \times j) \]

对于前两项，以第一项为例：由于没有了 \(i\) 和 \(j\) 的连体，每一项要么只含 \(i\)，要么只含 \(j\)。因此可以将 \(i\) 与 \(j\) 的求和独立看待：

\[\sum_{i=0}^{N_{0}}(C_{N_{0}}^{i}\times i^{2} \times \sum_{j=0}^{N_{1}} C_{N_{1}}^{j}) \]

其中有：

\[\sum_{j=0}^{N_{1}} C_{N_{1}}^{j} = 2^{N_{1}} \]

于是转化为：

\[2^{N_{1}} \times \sum_{i=0}^{N_{0}}(C_{N_{0}}^{i}\times i^{2}) \]

而后面的求和式有公式，可以直接计算。具体见下方博客链接。

对于第3项，也满足每一项只有 \(i\) 或者只有 \(j\)。因此可以写作：

\[\sum_{i=0}^{N_{0}}(C_{N_{0}}^{i} \times i \times \sum_{j=0}^{N_{1}}C_{N_{1}}^{j} \times j) \]

而后面一个求和式也是可以直接计算的，会得到一个常数。将该常数提出后，剩下的求和式又可以采用类似的方式计算。

这里只是想记录一些常见组合数求和计算公式以及对于求和式求解的拆解技巧，代码就先省略了(

组合数学公式blog