首先有一个 \(\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