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