首页 > 其他分享 >容斥定理

容斥定理

时间:2022-10-21 18:45:02浏览次数:55  
标签:错位 求解 定理 容斥 集合 题目 数目

用来求解集合计数问题,求解多个集合并的数目,转化为求交,结果等于加上奇数集合交的数目,将去偶数集合交的数目

经典题目求错位排列,反求不是错位排列的条件,在交集合的时候可以合并条件,题目一般反向求,将条件转化为多个子集合,在用二进制计数来表示集合

标签:错位,求解,定理,容斥,集合,题目,数目
From: https://www.cnblogs.com/xuanru/p/16814471.html

相关文章

  • 主定理
    主定理:将一个规模为n的问题,分治成a个\(\lceil\dfrac{n}{b}\rceil\)的子问题,每次带来的额外计算为\(\mathcal{O}(n^d)\),可得到以下关系式:\[T(n)=aT(\lceil\dfrac{n......
  • [安乐椅#3] 蝴蝶定理
    已知:抛物线\(C:y^2=2px(p>0)\),\(D(n,0),E(m,0)\)为其对称轴上两点,\(M\)是\(C\)上异于原点\(O\)的一动点,直线\(ME\)交\(C\)于\(N\),直线\(MD\)交\(C\)于\(......
  • 【高等数学基础进阶】微分中值定理及导数应用
    一、微分中值定理定理1(费马引理):如果函数$f(x)$在$x_{0}$处可导,且在$x_{0}$处取得极值,那么$f'(x_{0})=0$ 定理2(罗尔定理):若$f(x)$在$[a,b]$上连续$f(x)$在$(a,b)$......
  • luogu P5339 [TJOI2019]唱、跳、rap和篮球 (容斥,指数型母函数,NTT)
    https://www.luogu.com.cn/problem/P5339要求不含1234的方案,反过来求含至少一个1234的方案。钦定存在i个位置有1234,位置的方案是Cn-3i,i.其他n-4i个位置的方案是多重集......
  • 【笔记】裴蜀定理
    裴蜀定理:\[\foralla,b\in\mathbb{Z},\existsx,y\in\mathbb{Z},ax+by=\gcd(a,b)\]要求\(x,y\)不同时为\(0\)。推论:\[\begin{gathered}\text{对于}a,b\in......
  • 【模板】中国剩余定理
    中国剩余定理:同余方程组:\[x\equiva_i\pmod{m_i}\,(i\in\left[1,n\right])\](其中\(\foralli,j\in\left[1,n\right],\gcd(m_i,m_j)=1\))有解,且这些解构成一个......
  • Luogu2167 Bill的挑战 - 容斥 - dp -
    题目链接:https://www.luogu.com.cn/problem/P2167题解:摘录一段描述容斥题目的话:本题中,关于容斥系数,可以先感性理解一下,严格证明可以用即除了自身,自身的超集都计算......
  • CF1713F Lost Array(FWT,卢卡斯定理,*)
    CF1713FLostArray矩阵\(b[0\toN][0\toN]\)。\(b[i][0]=0\),\(b[0][i](i>1)=a[i]\)。\(b[i][j]=b[i-1][j]\oplusb[i][j-1]\)。给出\(c[1\toN]=b[......
  • AcWing算法提高课 容斥原理
    容斥原理的复杂度是2^n,一般n不会很大形如:  由于容斥原理一共有2^n中选法,可以用二进制枚举,1表示选择某个条件。然后将偶数个1的状态加起来,奇数个1的状态减去例题:ht......
  • 费用流消圈定理
    有负权环的费用流直接跑EK会死循环,根据消圈定理:该最小费用流最后的残余网络不存在负权环。可以提前消去负权环,boolclear_circle(int&cost){memset(cnt,0,sizeof......