Loading...

min-max容斥初学

check评论:0 条 remove_red_eye浏览量:203 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2019-12-20

容斥的一般式子,$W=\sum\limits_{T\subseteq S}^{|T|\leq |S|} f(T)\times w(T)$,其中$f(T)$代表$T$的容斥系数,一般是$-1^{|T|}$或$-1^{|T|-1}$

举个简单的例子,求欧拉函数$\varphi(\varphi(x)=\sum\limits_{i=1}^x [gcd(i,x)=1])$

我们考虑容斥,$\varphi(x)=x-\sum\limits_{i=1}^x [gcd(i,x)\not= 1]$

就可以先筛掉同时是一个数倍数的数,然后减去同时是两个的,加上同时是三个的...以此类推

$\min-\max$容斥

$\max(S)=\sum\limits_{T\subseteq S}\min(T)\times -1^{|T|-1}$

可以构造一个映射$f(T)$,设$x$为最大值,$f(T)\rightarrow f(T\oplus x)$,显然是一个一一映射,且一个映射的最小值相同可以抵消,就只剩下$x$的贡献了

$\min$也可以用$\max$容斥出来

例题:$PKUWC2018$随机游走

扩展$\min- \max $容斥

定义$\max(S,k)$代表集合$S$中第$k$大的元素

则$\max(S,k)=\sum\limits_{T\subseteq S}f(|T|)\times \min(T)$

我们希望第$t$大的元素的系数为$[t=k]$,则

$\sum\limits_{i=1}^t \left(\begin{matrix}t-1\\i-1\end{matrix}\right)f(i)=[t=k]$

$f(n)=\sum\limits_{i=1}^n (-1)^{n-i}\left(\begin{matrix}n-1\\ i-1 \end{matrix}\right)[i=k]$

$f(n)=(-1)^{n-k}\left(\begin{matrix}n-1\\k-1\end{matrix}\right)$

则$\max(S,k)=\sum\limits_{T\subseteq S}(-1)^{|T|-k}\left(\begin{matrix}|T|-1\\k-1\end{matrix}\right)\min(T)$

例题洛谷$P4707$重返现世

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名