异或
一、介绍 异或，英文为exclusive OR，缩写成xor 异或是一个数学运算符。它应用于逻辑运算。异或的数学符号为“⊕”，计算机符号为“xor”。其运算法则为： a⊕b = (¬a ∧ b) ∨ (a ∧¬b)（¬是非的意思，专门否定一个命题，p与¬p一真一假） 如果a、b两个值不相同，则异或结果为1。如果a、b两个值相同，异或结果为0。 异或也叫半加运算，其运算法则相当于不带进位的二进制加法：二进制下用1表示真，0表示假，则异或的运算法则为：0⊕0=0，1⊕0=1，0⊕1=1，1⊕1=0（同为0，异为1），这些法则与加法是相同的，只是不带进位，所以异或常被认作不进位加法。 异或略称为XOR、EOR、EX-OR 使用方法如下： z = x ⊕ y z = x xor y 计算机符号为：xor 计算机键盘上的符号：^ 二、运算法则 1. a ⊕ a = 0 2. a ⊕ 0 = a 3. a ⊕ b = b ⊕ a 4. a ⊕b ⊕ c = a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c; 5. d = a ⊕ b ⊕ c 可以推出 a = d ⊕ b ⊕ c. 6. a ⊕ ...
容斥原理
当交集比并集更好计算时，可以通过容斥原理来转化： ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣|A ∪B| = |A| + |B| − |A ∩B| ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣ ∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣A∩C∣−∣B∩C∣+∣A∩B∩C∣|A ∪B∪C| = |A| + |B| + |C| − |A ∩B| − |A ∩C| − |B∩C| + |A ∩B∩C| ∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣A∩C∣−∣B∩C∣+∣A∩B∩C∣ 更一般的形式： <img src="https://img2020.cnblogs.com/blog/1928767/202010/1928767-20201004175553721-1673457750.png" style="zoom: 50%;" /> 证明：考虑集合中每个元素对等式两边的贡献。 对上式两侧取补集，并运用德摩根律，整理得 <img src="https://img2020.cnblogs.com/blog/192 ...
线性筛
在这里提供三种线性筛的讲解,它们分别是:素数筛,欧拉筛和莫比乌斯筛。 筛法正确性的重要理论依据： 上述函数均为积性函数。积性函数的性质为:若f(x)是一个积性函数,那么对于任意素数a,b,满足f(ab)=f(a)*f(b) 一些可爱的要点(有助于理解筛法原理)： 1.欧拉筛和莫比乌斯筛是以素数筛为基础的。 2.三者在代码实现上几乎是同一框架。 3.欧拉函数和莫比乌斯函数的定义介绍： (1)欧拉函数Phi(x)表示小于等于x的正整数中和x互质的数的个数(注意,1与任何数互质)。 (2)莫比乌斯函数Mob(x)仅有三种值:0,-1,1————如果x能够被一个大于0的整数的平方整除，那么函数值为0;如果x拥有奇数种 质因数，那么函数值为-1，有偶数种质因数，那么函数值为1(莫比乌斯函数的神奇定义决定了它应用于容斥问题…)。 线性筛的两大步骤： (1)获得范围内的素数 线性筛的线性体现在尽可能的使每个数只被“筛”一次。其思想众所周知地基于： a为任何数,b为质数,那么a*b就不是质数。 在程序实现中体现为，对于当前枚举的数i,使用所有小于等于i的素数p，去“筛除”数(p * i),即将布尔数组 ...
乘法逆元
如果尝试对取模后的结果直接进行除法运算，可能会出现除不尽的问题， 这时候就需要用到乘法逆元。 乘法逆元有着类似倒数的性质：对于正整数 xxx，如果存在正整数 yyy，满足 xy≡1(modxy ≡ 1 (modxy≡1(mod p)p)p) 则 x,yx,yx,y 互为模 ppp 意义下的乘法逆元。 当我们想做除法运算时，可以用乘上对应的乘法逆元来代替。 当 xxx 与 ppp 互素时，存在唯一的 xxx 的逆元。当 ppp 是素数时，所有不是 ppp的倍数的整数都有唯一的逆元，所以大部分题目都会对素数取模。 扩展欧几里得算法求逆元 求逆元就是求如下方程的解： ax≡1(modax ≡ 1 (modax≡1(mod p)p)p) 也就是 ax−kp=1,k∈Zax − kp = 1,k ∈ Zax−kp=1,k∈Z 假如 gcd(a,p)=1gcd(a, p) = 1gcd(a,p)=1（也就是逆元存在的条件），就可以用扩欧来计算 xxx了。注意结果可能是负数，此时需要再加上 ppp。 利用费⻢小定理求逆元 根据费⻢小定理 ap−1≡1(moda^{p−1} ≡ 1 (modap−1≡ ...
树状数组
先来看几个问题吧。 1.什么是树状数组？ 顾名思义，就是用数组来模拟树形结构呗。那么衍生出一个问题，为什么不直接建树？答案是没必要，因为树状数组能处理的问题就没必要建树。和TrieTrieTrie树的构造方式有类似之处。 2.树状数组可以解决什么问题 可以解决大部分基于区间上的更新以及求和问题。 3.树状数组和线段树的区别在哪里 树状数组可以解决的问题都可以用线段树解决，这两者的区别在哪里呢？树状数组的系数要少很多，就比如字符串模拟大数可以解决大数问题，也可以解决1+11+11+1的问题，但没人会在1+11+11+1的问题上用大数模拟。 4.树状数组的优点和缺点 修改和查询的复杂度都是O(logN)O(logN)O(logN)，而且相比线段树系数要少很多，比传统数组要快，而且容易写。 缺点是遇到复杂的区间问题还是不能解决，功能还是有限。 一、树状数组介绍 二叉树大家一定都知道，如下图 每个位置只有一个方框，令每个位置存的就是子节点的值的和，则有 C[1]=A[1];C[1] = A[1];C[1]=A[1]; C[2]=A[1]+A[2];C[2] = A[1] + A[2];C[2 ...
倍增
一、ST表 1.预处理 f[i][j]f[i][j]f[i][j]表示从i开始的长度为2j的区间（（（即区间[i,i+2j−1]）[i,i+2j−1]）[i,i+2j−1]） 递推公式（j（j（j在外层递增）：）：）： f[i][j]=maxf[i][j−1],f[i+2j−1][j−1]f[i][j]=max{f[i][j−1],f[i+2j−1][j−1]} f[i][j]=maxf[i][j−1],f[i+2j−1][j−1] 即将区间[l,r][l,r][l,r]分为两个区间合并 2.查询 分为两段，第一段为区间[l,2k][l,2k][l,2k]，第二段为区间[r−2k+1,r][r−2k+1,r][r−2k+1,r]，其中kkk为满足2k≤r−l+12k≤r−l+12k≤r−l+1的所有数中最大的那个数 即区间[l,r][l,r][l,r]的最大值为maxf[l][k],f[r−2k+1][k]max{f[l][k],f[r−2k+1][k]}maxf[l][k],f[r−2k+1][k] 3.例子 忠诚 洛谷 P1816 多次查询区间最小值 123456789101112 ...
幂
一、相关介绍 幂（power）是指乘方运算的结果。nmn^mnm指该式意义为m个n相乘。把nmn^mnm看作乘方的结果，叫做n的m次幂，也叫n的m次方。 数学中的“幂”，是“幂”这个字面意思的引申，“幂”原指盖东西布巾，数学中“幂”是乘方的结果，而乘方的表示是通过在一个数字上加上标的形式来实现的，故这就像在一个数上“盖上了一头巾”，在现实中盖头巾又有升级的意思，所以把乘方叫做幂正好契合了数学中指数级数快速增长含义，形式上也很契合，所以叫做幂。 幂不符合结合律和交换律。 因为十的次方很易计算，只需在后加零即可，所以科学记数法借助此简化记录数的方式；二的次方在计算机科学中很有用。 二、定义 幂指乘方运算的结果。nmn^mnm指mmm个nnn相乘。把nmn^mnm看作乘方的结果，叫做nnn的mmm次幂。 其中，nnn称为底数，mmm称为指数（写成上标）。当不能用上标时，例如在编程语言或电子邮件中，通常写成nmn^mnm或n∗∗mn**mn∗∗m，亦可以用高德纳箭号表示法，写成n↑mn↑mn↑m，读作“nnn的mmm次方”或者nnn的mmm次幂。 当指数为111时，通常不写出来，因为那和底的数 ...
列表
列表 一、append( )方法 原地修改列表对象，是真正的列表尾部添加新的元素，速度最快，推荐使用 1234>>> a = [20, 40]>>> a append(80)>>> a[20, 40, 80] 二、加法运算符 并不是真正的尾部添加元素，而是创建新的列表对象；将原列表的元素和新列表的元素依次复制到新的列表对象中。这样，会涉及大的复制操作，对于操作大量元素不建议使用。 123456>>> a = [20, 40]>>> id(a)28484854784>>> a=a+[50]>>> id(a)28481420352 通过如上测试，我们发现变量a的地址发生了变化。也就是创建了新的列表对象。 三、extend( )方法 将目标列表的所有元素添加到本列表的尾部，属于原地操作，不创建新的列表对象 123456>>> a = [20, 40]>>> id(a)28485031424>>> a.extend( ...
基本运算符
基本运算符 运算符 说明 or, and, not 布尔或、布尔与、布尔非 is, is, not 判断是否为同一个对象 <, <=, >, >=, ！=, == 比较值是否相当，可以连用 |, ^, & 按位成，按位异或、按位与 <<, >> 移位 ~ 按位翻转 +, -, *, /, //, % 加，减，乘，浮点除、整数除、取余 ** 幂运算 1.比较运算符可以连用，并且含义和我们日常使用完全一致 123>>> a=4>>> 3<a<10 #关系运算符可以连用True 2.位操作 123456789>>> a = 0b11001>>> b = 0b01000>>> c = a|b>>> bin(c) #bin( )可以将数字转成二进制表示"0b11001">>> bin(c&b)"0b10 ...
集合
集合 集合是无序可变，元素不能重复，实际上，集合底层是字典实现，集合的所有元素都是字典中的“键对象”，因此是不能重复的且唯一的。 集合创建和删除 1.使用创建集合对象，并使用add( )方法添加元素 123456>>> a = {3, 5, 7}>>> a{3, 5, 7}>>> a.add(9)>>> a{9, 3, 5, 7} 2.使用set( )，将列表、元组等可迭代对象转成集合，如果原来数据存在重复数据，则只保留一个 1234>>> a = ["a", "b", "c", "b"]>>> b = set(a)>>> b{'a', 'c', 'b'} 集合相关操作 1234567891011121314>>> a = ...
