欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

二项式反演/minmax容斥初探

程序员文章站 2022-06-03 18:57:28
世界是物质的,物质是运动的,运动是有规律的,规律是可以被认识的 二项式反演 $$ g_n=\sum_{i=0}^n \binom{n}if_i\Rightarrow f_n=\sum_{i=0}^n( 1)^{n i}\binom{n}ig_i $$ 证明如下 $$ \begin{aligned} ......

世界是物质的,物质是运动的,运动是有规律的,规律是可以被认识的

二项式反演

\[ g_n=\sum_{i=0}^n \binom{n}if_i\rightarrow f_n=\sum_{i=0}^n(-1)^{n-i}\binom{n}ig_i \]

证明如下

\[ \begin{aligned} \sum_{i=0}^n(-1)^{n-i}\binom{n}ig_i &=\sum_{i=0}^n(-1)^{n-i}\binom{n}i\sum_{j=0}^i\binom{i}jf_i\\ &=\sum_{j=0}^nf_i \sum_{i=j}^n(-1)^{n-i}\binom{n}i\binom{i}j\\ &=\sum_{j=0}^nf_i \sum_{i=j}^n(-1)^{n-i}\binom{n}j\binom{n-j}{i-j}\\ &=\sum_{j=0}^n\binom{n}jf_j \sum_{i=j}^n(-1)^{n-i}\binom{n-j}{i-j}\\ &=\sum_{j=0}^n\binom{n}jf_j \sum_{i=0}^{n-j}(-1)^{n-j-i}\binom{n-j}i\\ &=\sum_{j=0}^n\binom{n}jf_j\times (1-1)^{n-j} \end{aligned} \]

在默认\(0^0=1\)的情况下,显然

\[ \sum_{j=0}^n\binom{n}jf_j\times (1-1)^{n-j}=f_n\\ f_n=f_n \]

最值反演

\[ \max(s)=\sum_{t\subseteq s} (-1)^{|t|-1}\min(t)\\ e_\forall(s)=\sum_{t\subseteq s} (-1)^{|t|-1}e_\exists(t)\\ \text{lcm}(s)=\prod_{t\subseteq s} (-1)^{|t|-1}\gcd(t)\\ \]

其中,\(s,t\not=\varnothing\)

推导第一类

设系数函数\(f\)满足
\[ \max(s)=\sum_{t\subseteq s} f(|t|)\min(t) \]

考虑\(s\)中第\(x+1\)大元素作为子集的最小值的情况数,显然
\[ \sum_{i=0}^x\binom{x}if(i+1) = [x=0]\\ f(x+1)=\sum_{i=0}^x(-1)^{x-i}\binom{x}i[i=0]=(-1)^x \]
于是\(f(x)=(-1)^{x-1}\)

扩展
\[ \text{maxk}(s)=\sum_{t\subseteq s} f(|t|)\min(t) \]
此时需要满足
\[ \sum_{i=0}^x\binom{x}if(i+1) = [x=k-1]\\ f(x+1)=\sum_{i=0}^x(-1)^{x-i}\binom{x}i[i=k-1]=(-1)^{x-k+1}\binom{x}{k-1} \]
\(f(x)=(-1)^{x-k}\binom{x-1}{k-1}\)
\[ \text{maxk}(s)=\sum_{t\subseteq s}(-1)^{|t|-k}\binom{|t|-1}{k-1}\min(t) \]