首先有一个 \(\mathcal O(N^2)\) 做法。
考虑容斥掉条件一，令 \(g(i)\) 表示恰好有 \(i\) 个花园空着，\(f(i)\) 表示至少有 \(i\) 个花园空着。
则有 \(g(0)=\sum\limits_{i=0}^{N}(-1)^if(i)\)。
而
\[f(i)=\binom{N}{i}\sum_{a=0}^{\min(A,N-i)}\binom{N-i}{a}\times \sum_{b=0}^{\min(B,N-i)}\binom{N-i}{b}\times \sum_{c=0}^{\min(C,N-i)}\binom{N-i}{c} \]因此
\[g(0)=(-1)^i\binom{N}{i}\sum_{a=0}^{\min(A,N-i)}\binom{N-i}{a}\times \sum_{b=0}^{\min(B,N-i)}\binom{N-i}{b}\times \sum_{c=0}^{\min(C,N-i)}\binom{N-i}{c} \]直接做是 \(\mathcal O(n^2)\) 的，Code。
考虑写的好看一点，变成：
\[(-1)^{N-i}\binom{N}{i}\sum_{a=0}^{\min(A,i)}\binom{i}{a}\times \sum_{b=0}^{\min(B,i)}\binom{i}{b}\times \sum_{c=0}^{\min(C,i)}\binom{i}{c} \]先把这个式子放一放，令
\[f_M(N)=\sum\limits_{i=0}^{\min(N,M)}\dbinom{N}{i} \]初值为 \(f_M(0)=1\)。
则可以 \(\mathcal O(1)\) 计算出
\[f_M(N+1)=\sum\limits_{i=0}^{\min(N+1,M)}\dbinom{N+1}{i} \]当 \(N+1\le M\) 时，则有
\[f_M(N+1)=\sum\limits_{i=0}^{N+1}\dbinom{N+1}{i}=2^{N+1} \]所以
\[f_M(N+1)=2\times f_M(N) \]那么如果 \(N+1\gt M\) 时呢？
考虑放在一张网格图上，借用一下官方题解的图：
考虑两者之间的联系，一个是走 \(N\) 步走到一个红色点的方案数，一个是走 \(N+1\) 步走到一个蓝色点的方案数。
发现从任意一个红色点，向上和向右都能走到一个蓝色点，除了最下面的点，它只能向上走到一个蓝色点，不难发现走到这个点的方案数就是 \(\dbinom{N}{M}\)。
所以
\[f_M(N+1)=2\times f_M(N)-\binom{N}{M} \]但是你发现 \(N\lt M\) 即 \(N+1\le M\) 的时候，\(\dbinom{N}{M}=0\)，所以其实两者的式子是一样的。
由此，可以在 \(\mathcal O(1)\) 内由
\[\sum_{a=0}^{\min(A,i)}\binom{i}{a},\sum_{b=0}^{\min(B,i)}\binom{i}{b}, \sum_{c=0}^{\min(C,i)}\binom{i}{c} \]推出
\[\sum_{a=0}^{\min(A,i+1)}\binom{i+1}{a},\sum_{b=0}^{\min(B,i+1)}\binom{i+1}{b}, \sum_{c=0}^{\min(C,i+1)}\binom{i+1}{c} \]于是总时间复杂度 \(\mathcal O(N)\)。
标签：dbinom,min,sum,ABC235G,times,mathcal,binom From： https://www.cnblogs.com/Kobe303/p/16871500.html