P7481 梦现时刻
由题得：
\[F(a, b) = \sum_{i = 0} ^ {b}\dbinom{b}{i}\dbinom{n - i}{a} \]根据公式 \(\displaystyle \dbinom{n}{m} = \dbinom{n - 1}{m - 1} + \dbinom{n - 1}{m}\)，有：
\[F(a, b) = \sum_{i = 0} ^ {b}\dbinom{b - 1}{i - 1}\dbinom{n - i}{a} + \sum_{i = 0} ^ {b}\dbinom{b - 1}{i}\dbinom{n - i}{a} \]\[F(a, b) = \sum_{i = 0} ^ {b}\dbinom{b - 1}{i - 1}\dbinom{n - i}{a} + F(a, b - 1) \]好的我们发现这个式子烦人的一点就是 \(\displaystyle \sum_{i = 0} ^ {b}\dbinom{b - 1}{i - 1}\dbinom{n - i}{a}\)，考虑将其也写成若干个 \(F\) 乘系数的形式。
\[\displaystyle \sum_{i = 0} ^ {b}\dbinom{b - 1}{i - 1}\dbinom{n - i}{a} = \sum_{i = -1} ^ {b - 1}\dbinom{b - 1}{i}\dbinom{n - i - 1}{a} \]\[= \sum_{i = -1} ^ {b - 1}\dbinom{b - 1}{i}\dbinom{n - i}{a} - \sum_{i = -1} ^ {b - 1}\dbinom{b - 1}{i}\dbinom{n - i - 1}{a - 1} \]\[= F(a, b - 1) - \sum_{i = -1} ^ {b - 1}\dbinom{b - 1}{i}\dbinom{n - i - 1}{a - 1} \]现在的目标转化为化简 \(\displaystyle \sum_{i = -1} ^ {b - 1}\dbinom{b - 1}{i}\dbinom{n - i - 1}{a - 1}\)，继续：
\[\sum_{i = -1} ^ {b - 1}\dbinom{b - 1}{i}\dbinom{n - i - 1}{a - 1} = \sum_{i = -1} ^ {b - 1}\dbinom{b}{i + 1}\dbinom{n - i - 1}{a - 1} - \sum_{i = -1} ^ {b - 1}\dbinom{b - 1}{i + 1}\dbinom{n - i - 1}{a - 1} \]\[= \sum_{i = 0} ^ {b}\dbinom{b}{i}\dbinom{n - i}{a - 1} - \sum_{i = 0} ^ {b}\dbinom{b - 1}{i}\dbinom{n - i}{a - 1} \]因为 \(\dbinom{b - 1}{b} = 0\)，所以有：
\[= \sum_{i = 0} ^ {b}\dbinom{b}{i}\dbinom{n - i}{a - 1} - \sum_{i = 0} ^ {b - 1}\dbinom{b - 1}{i}\dbinom{n - i}{a - 1} \]\[= F(a - 1, b) - F(a - 1, b - 1) \]整理一下，有：
\[\displaystyle \sum_{i = -1} ^ {b - 1}\dbinom{b - 1}{i}\dbinom{n - i - 1}{a - 1} = F(a - 1, b) - F(a - 1, b - 1) \]\[\displaystyle \sum_{i = 0} ^ {b}\dbinom{b - 1}{i - 1}\dbinom{n - i}{a} = F(a, b - 1) - (F(a - 1, b) - F(a - 1, b - 1)) \]\[\displaystyle \sum_{i = 0} ^ {b}\dbinom{b - 1}{i - 1}\dbinom{n - i}{a} = F(a, b - 1) - F(a - 1, b) + F(a - 1, b - 1) \]\[F(a, b) = F(a, b - 1) - F(a - 1, b) + F(a - 1, b - 1) + F(a, b - 1) \]\[F(a, b) = 2F(a, b - 1) - F(a - 1, b) + F(a - 1, b - 1) \]好的！我们现在得到了递推式，可以 \(O(m ^ 2)\) 计算，但是考虑一些边界情况：
\[F(0, b) = 2^b \]\[F(a, 0) = \dbinom{n}{a} \]因为 \(n \leq 10^9\)，所以需要使用以下公式计算：
\[\dbinom{n}{a} = \dfrac{\displaystyle \prod_{i = n - a + 1} ^ {n} i}{a!} \] 标签：dbinom,记录,公式,sum,数学,Maths,displaystyle From： https://www.cnblogs.com/RB16B/p/18019850