二项式

标签：满足条件 sum choose alpha 二项式 dp

二项式定理

\[(x+y)^{n}=\sum_{i=0}^{n}{n\choose i}x^{i}y^{n-i} \]

多元二项式定理：

\[(x_{1}+\cdots+x_{k})^{n}=\sum_{\sum m_{i}=n}{n\choose m_{1},m_{2},\cdots,m_{k}}x_{1}^{m_{1}}x_{2}^{m_{2}}\cdots x_{k}^{m_{k}} \]

广义二项式定理：

\[(x+y)^{\alpha}=\sum_{i=0}^{\infty}{\alpha\choose i}x^{i}y^{\alpha-i},\alpha\in\mathbb{R} \]

其中 \(\displaystyle{\alpha\choose i}=\frac{\alpha^{\underline{ｉ}}}{i!}\)

特殊情况

• \(a=b=1\)：

\[\sum_{i=0}^{n}{n\choose i}=2^{n} \]

• \(a=-1,b=1\)：

\[\sum_{i=0}^{n}(-1)^{i}{n\choose i}=[n=0] \]

二项式反演

形式

共四种形式：子集与超集，「至多/至少」与「恰好」（并不准确）

\[f(n)=\sum_{i=m}^{n}(-1)^{i}{n\choose i}g(i)\iff g(n)=\sum_{i=m}^{n}(-1)^{i}{n\choose i}f(i) \]

\[f(n)=\sum_{i=n}(-1)^{i}{i\choose n}g(i)\iff g(n)=\sum_{i=n}(-1)^{i}{i\choose n}f(i) \]

\[f(n)=\sum_{i=m}^{n}{n\choose i}g(i)\iff g(n)=\sum_{i=m}^{n}(-1)^{n-i}{n\choose i}f(i) \]

\[f(n)=\sum_{i=n}{i\choose n}g(i)\iff g(n)=\sum_{i=n}(-1)^{i-n}{i\choose n}f(i) \]

一般情况下 \(m=0\)

其实前两种和后两种的区别就是移动 \(-1\) 的幂，后两种更常用

组合意义

形式 \(3\)：\(f(n)\) 为至多 \(n\) 个满足条件。可以有 \(i\le n\) 个满足条件， 先确定出这 \(i\) 个，再乘上恰好 \(i\) 个满足条件的方案数
形式 \(4\)：\(f(n)\) 为至少 \(n\) 个满足条件。恰好 \(i\ge n\) 个满足条件的方案数在钦定的元素（\(n\) 个）是满足条件的元素（\(i\) 个）的子集时会被计算一次，共 \({i\choose n}\) 次

证明

以形式 \(3\) 为例

\[f(n)=\sum_{i=m}^{n}{n\choose i}\sum_{j=m}^{i}(-1)^{i-j}{i\choose j}f(j) \\ =\sum_{i=m}^{n}\sum_{j=m}^{i}(-1)^{i-j}{n\choose i}{i\choose j}f(j) \\ =\sum_{i=m}^{n}\sum_{j=m}^{i}(-1)^{i-j}{n\choose j}{n-j\choose i-j}f(j) \\ =\sum_{j=m}^{n}\sum_{i=j}^{n}(-1)^{i-j}{n\choose j}{n-j\choose i-j}f(j) \\ =\sum_{j=m}^{n}{n\choose j}f(j)\sum_{i=0}^{n-j}(-1)^{i}{n-j\choose i} \\ =\sum_{j=m}^{n}{n\choose j}f(j)[n=j] \\ =f(n) \]

二维

以形式 \(4\) 为例

\[f(x,y)=\sum_{i=x}^{n}\sum_{j=y}^{n}{i\choose x}{j\choose y}g(i,j)\iff g(x,y)=\sum_{i=x}^{n}\sum_{j=y}^{n}(-1)^{i-x+j-y}{i\choose x}{j\choose y}f(i,j) \]

题目

bzoj2839 集合计数

设 \(f(m)\) 为交集元素至少为 \(m\) 的方案数，\(g(m)\) 为恰好，则

\[f(m)={n\choose m}(2^{2^{n-m}}-1)=\sum_{i=m}^{n}{i\choose m}g(i) \]

套公式反演出 \(g\) 即可

LG4859 已经没有什么好害怕的了

下文的 \(k\) 表示糖果比药片能量大的组数恰好为 \(k\)（即题目中的 \(\frac{n+k}{2}\)）

先将糖果、药片分别排序，记 \(cnt[i]\) 为有多少个药片小于第 \(i\) 个糖果。由于组与组顺序无关，可以看做糖果升序时有多少种药片的排列满足条件

发现题目中的「恰好」很难做，考虑二项式反演，变为求出钦定 \(k\) 组

设 \(dp[i,j]\) 为前 \(i\) 个糖果有 \(j\) 组比药片大，则有 \(dp[i,j]=dp[i-1,j]+(cnt[i]-j+1)dp[i-1,j-1]\)，钦定 \(i\) 组的方案数即为 \(dp[n,i]\times(n-i)!\)，然后反演出恰好 \(k\) 组的即可

复杂度 \(O(n^{2})\)，瓶颈在于 DP

标签：满足条件,sum,choose,alpha,二项式,dp
From： https://www.cnblogs.com/ft61/p/18294321