位运算

运算符&函数

位运算符与&、或|、异或^、取反~、补码-、左移<<、右移>>；内建函数，在函数名末尾添加l或ll可使参数类型变为long或long long
int __builtin_ffs(int x) 返回x二进制末尾最后一个1的位置，最低位编号为1。当x为0时返回0
int __builtin_clz(unsigned int x) 返回x二进制前导0的个数。当x为0时结果未定义
int __builtin_ctz(unsigned int x) 返回x二进制末尾连续0的个数。当x为0时结果未定义
int __builtin_popcount(unsigned int x) 返回x二进制中1的个数
int __builtin_parity(unsigned int x) 返回x二进制中1的个数的奇偶性

bitset

更多位数使用 bitset，包含头文件 bitset

$B$ 进制数

template <long long B>
struct Base{//进制为 B 
	sc long long pw[N];// pw[i] 为 B的 i 次方
	long long v;//存储数值
	Base(long long val=0):v(val){}
	sc void init(){//只需调用一次 Base<B>::init()
		pw[0]=1;
		for(int i=1; i<N; ++i){
			pw[i]=pw[i-1]*B;
		}
	}
	inline long long get(int i){
		return (v/pw[i])%B;// 通过整除和取余计算第 i 位的值
	}
    
    inline void set(int i, long long x) {// 设置第 i 位的数值为 x
        long long cur = get(i);// 获取当前第 i 位的数值
		v+=(x-cur)*pw[i];// 计算需要改变的差值，并修改原数值
    }
};
template <long long B>
long long Base<B>::pw[N];

位运算应用

高效进行运算
表示集合（状压DP）
题目要求进行位运算

异或性质

$a\oplus b=x \iff a\oplus x=b$
$a[l,r]=a[1,r]\oplus a[1,l-1]$

二进制集合运算

模2的幂

对2的非负整数次幂取模等价于取二进制下一个数的后若干位，等价于 和 mod-1 进行与操作
判断一个数是不是2的非负整数次幂
- n为2的非负整数次幂，当且仅当n的二进制只有一个1时，等价于 n>0 && (n&(n-1))==0

子集遍历

掩码是一串二进制码，用于和源码进行与运算，得到屏蔽源码的若干输入位后的新操作数。掩码的1位保留源码相应位，0则屏蔽
给定掩码 m，使用 s=(s-1)&m 降序生成掩码 m 的所有子掩码

遍历所有掩码的子掩码

$O(3^n)$ n为掩码总共的位数，即集合中元素的总数

整除

素数

定义

无法被除1和自身以外的数整除的数

优化

对于合数n必定存在素数 $p \leqslant \sqrt{n}$ 使得p|n，否则n为素数

应用

结合算术基本定理将整数分解为素数幂之积

最大公约数

实现

gcd(a,b): 欧几里得算法 O(log max(a,b))，更相减损术（针对高精度大整数）
由gcd(a,b)*lcm(a,b)=a*b，最小公倍数lcm(a,b)=a*b/gcd(a,b)

优化

由算术基本定理，最大公约数是素数幂之积取幂的最小值，最小公倍数是素数幂之积取幂的最大值

应用

求多个数的最大公约数先求一个最大公约数然后与下一个数求最大公约数，直到求完所有最大公约数；多个数的最小公倍数直接将最小公倍数放入最大公约数处理过程中去处理，最后得到的一定是最小公倍数

代码

//递归
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
//迭代
int gcd(int a, int b) {
  while (b != 0) {
    int tmp = a;
    a = b;
    b = tmp % b;
  }
  return a;
}
void lcm(int a, int b){return a/gcd(a,b)*b;}

扩展欧几里得算法

实现

递归实现，迭代实现。求出的可行解必有 $|x|<=b$ ， $|y|<=a$

思想

贝祖等式（对任意整数x和y，满足gcd(a,b)|ax+by，存在整数使得ax+by=gcd(a,b) ）

应用

求 ax+by=gcd(a,b) 的一组可行解
求乘法逆元

代码

//递归，返回gcd，求出x和y
//EXGCD
ll EXGCD(ll a, ll b, ll &x, ll &y) {
  if (!b) {
    x = 1;
    y = 0;
    return a;
  }
  ll d = EXGCD(b, a % b, x, y);
  ll t = x;
  x = y;
  y = t - (a / b) * y;
  return d;
}
//迭代
int exgcd(int a, int b, int& x, int& y) {
  x = 1, y = 0;
  int x1 = 0, y1 = 1, a1 = a, b1 = b;
  while (b1) {
    int q = a1 / b1;
    tie(x, x1) = make_tuple(x1, x - q * x1);
    tie(y, y1) = make_tuple(y1, y - q * y1);
    tie(a1, b1) = make_tuple(b1, a1 - q * b1);
  }
  return a1;
}

欧拉函数

实现

直接根据定义质因数分解的同时求 $\phi(n)=\prod((p-1)/p)$ 其中p是整除n的素数；线性筛求欧拉函数

优化

欧拉函数是积性函数， $\phi(a\times b)=\phi(a)\times\phi(b)$
线性筛法求多个数的欧拉函数值

应用

结合欧拉定理优化快速幂运算

代码

int phi(int n) {
    int m = floor(sqrt(n + 0.5)), ans = n;
    for (int i = 2; i <= m; i++) {
        if (n % i == 0) {
            ans = ans / i * (i - 1);//积性函数
            while (n % i == 0) n /= i;//质因数分解
        }
    }
    if (n != 1) ans = ans / n * (n - 1); // 前面没筛干净的
    return ans;
}

素数筛法

实现

埃氏筛

任意大于 $1$ 的合数 $n$ 必定有不超过 $\sqrt{n}$ 的质因子。对于任意质数 $x$ ，其倍数 $kx,k\geq 2$ 必定是合数。

$O(n\log\log n)$

vector<int> pri;//记录素数
void getpri(int n){
    static bitset<N> not_pri;//非素数标记
    for(int i=2; i*i<=n; ++i){//筛到 sqrt(n)
        if(not_pri[i]) continue;
        for(int j=i*i; j<=n; j+=i) not_pri.set(j);//素数的倍数非素数
    }
    for(int i=2; i<=n; ++i) if(!not_pri[i]) pri.push_back(i);
}

线性筛

任意大于 $1$ 的整数 $x$ 与质数集合 $\set{p|p\leq x}$ 的乘积必定是合数，若 $p|x$ 则合数 $x$ 之前被 $p$ 筛过且$x$ 与更大质数的乘积也被筛过。

$O(n)$

vector<int> pri;
void getpri(int n){
    static bitset<N> not_pri;
    not_pri.reset();
    for(int i=2; i<=n; ++i){
        if(!not_pri[i]) pri.push_back(i);
        for(auto&& j : pri){
            if(i*j>n) break;
            not_pri.set(i*j);
            if(i%j==0) break;//意味着 i 之前被 j 筛过，故 i 与更大质数的结果也被筛过
        }
    }
}

区间筛

筛选 $[l,r]$ 内素数，转化为标记 $[l,r]$ 内合数。

在 $[1,\sqrt{r}]$ 内必有 $r$ 的质因子，先在 $[1,\sqrt{r}]$ 中进行线性筛预处理，然后用筛选的的质因子在 $[l,r]$ 内进行埃氏筛求出所有合数，剩下未标记的即素数。

$O(\sqrt{r}+(r-l)\log\log(r-l))$

vector<int> pri;
void getpri(int n){
    static bitset<N> not_pri;
    not_pri.reset();
    for(int i=2; i<=n; ++i){
        if(!not_pri[i]) pri.push_back(i);
        for(auto&& j : pri){
            if(i*j>n) break;
            not_pri.set(i*j);
            if(i%j==0) break;//意味着 i 之前被 j 筛过，故 i 与其他质数的结果也被筛过
        }
    }
}
vector<ll> pri2;
void getpri(ll l, ll r){
    static bitset<N> not_pri;
    not_pri.reset();
    l=max(l, 2ll);
    int m=sqrt(r);
    getpri(m);//获取[1,sqrt(r)]的所有质因子
    ll t;
    for(auto&& i : pri){
        t=(l+i-1)/i*i;
        t=max(t, ll(i<<1));
        for(ll j=t; j<=r; j+=i) not_pri.set(j-l);//埃氏筛
    }   
    for(int i=0; i<=r-l; ++i) if(!not_pri[i]) pri2.push_back(l+i); 
}

应用

求欧拉函数、求莫比乌斯函数、求约数个数、求约束和

同余方程

线性同余方程&乘法逆元

定义

线性同余方程：形如 $ax \equiv b(modm)$ 的方程，其中 $x \in [0, n-1]$
乘法逆元： $a \cdot a^{-1}=1(modm)$ ，称 $a^{-1}$ 为 $amodb$ 的逆元

应用

有理数取余： $c={a \over b} modm=a \cdot b^{-1} modm=a*qpow(b, m-2)modm$
乘法逆元/EXGCD 求解贝祖等式

欧拉定理&费马小定理

定义

欧拉定理：若 gcd(a, m)=1, 则 $a^{\phi(m)} \equiv 1(mod m)$
费马小定理：若p为素数，则 $a^{p-1} \equiv 1(mod p)$

思想

同余

应用

欧拉定理用于优化快速幂运算。
费马小定理用于求乘法逆元，然后求分数在模意义下的值

中国剩余定理

定义

求解如下形式线性方程组 ( $n_1, n_2,…,n_k$ 两两互质)
$\begin{cases} x \equiv b_1(mod n_1) \ x \equiv b_2(mod n_2) \ …\ x \equiv b_k(mod n_k)
\end{cases}$

过程

计算所有模数的积 n
对于第 i 个方程
1. 计算 $m_i={n \over {n_i}}$
2. 计算 $m_i$ 在模 $n_i$ 意义下的逆元 $m_i^{-1}$
3. 计算不对 $n_i$ 取模的 $c_i=m_im_i^{-1}$
方程在模n意义下的唯一解为 $x=\sum _{i=1}^k b_ic_i(modn)$

扩展

模数不互质的模线性同余方程组，存在以下规律：

合并的新方程的模数是之前模数的 LCM
可能无解

将两个方程等价然后移项得到
$k_1n_1-k_2n_2=b_2-b_1$
若 $d=gcd(n_1, n_2 )|b_2-b_1$ ，则有解，否则无解
用互质两数 $p_1={ {n_1} \over d},p_2={ {n_2} \over d}$ 代入式中
$k_1p_1-k_2p_2={ {b_2-b_1} \over d}$
通过 EXGCD 求解方程 $\lambda _1p_1+ \lambda _2p_2=1$ ，直接得到
$\begin{cases} k_1 = { {b_2-b_1} \over d}\lambda _1\ k_2 = -{ {b_2-b_1} \over d}\lambda _2 \end{cases}$
则特解 $x=b_1+{ {b_2-b_1} \over d}\lambda _1n_1$
定理：特解为 $x^$ ，通解为 $x^+k\cdot lcm(n_1, n_2)$ ，即 $x \equiv x^*(mod lcm(n_1, n_2))$

代码

//CRT x=bi(mod ni)
ll bi[N], ni[N];
ll CRT(int k) {
  ll n = 1, ans = 0;
  for (int i = 1; i <= k; i++) n = n * ni[i];
  for (int i = 1; i <= k; i++) {
    ll m = n / ni[i], x, y;
    EXGCD(m, ni[i], x, y);  // a * m mod bi[i] = 1
    ans = (ans + bi[i] * m * x % n) % n;
  }
  return (ans % n + n) % n;
}
//EXGCD x=bi (mod ni)
ll mul(ll a,ll b,ll mod)//保证不爆long long的乘法
{
    ll res=0;
    while(b>0)
    {
        if(b&1) res=(res+a)%mod;
        a=(a+a)%mod;
        b>>=1;
    }
    return res;
}
ll bi[N], ni[N];
ll EXCRT(int k)//递推形式合并方程，模数不互质可用
{
    ll x,y;
    ll m=ni[1],ans=bi[1];//第一个方程的解特判
    for(int i=2;i<=k;i++)
    {
        ll n=ni[i],c=(bi[i]-ans%n+n)%n;//ax≡c(mod n)
        ll gcd=EXGCD(m,n,x,y),ng=n/gcd;//EXGCD xm + yn=1 的 gcd 和 贝祖等式参数 x, y
        if(c%gcd) return -1; //判断是否无解
        x=mul(x,c/gcd,ng);//x是lambda1, c/gcd是 (b2-b1)/d, ng是模数
        ans+=x*m;//更新前k个方程组的答案
        m*=ng;//M为前k个m的lcm
        ans=(ans%m+m)%m;
    }
    return (ans%m+m)%m;
}

莫比乌斯反演

待补充

组合数学

计算公式

数列求和公式

等差数列求和公式 $S={ { \sum_{i=1}^n }{ a_1 }+{ (n-1)d } }= { { n { a_1 } }+{ { n(n-1)d } } \over { 2 } }={ { n(a_1+a_n) } \over { 2 } } $
等比数列求和公式 $S=\sum_{i=1}^na\times r^{i-1}={ a(1-r^n) \over {1-r} }$
平方和公式 $S={ { n(n+1)(2n+1) } \over { 6 } }$

排列组合

加法原理&乘法原理

n类方法，则加法；n个步骤，则乘法

排列数

$A(n, m)={ { n! } \over { (n-m)! } }$
从n个元素中取出m个的所有排列个数

组合数

$C(n, m)={ {A(n, m)}\over{m!} }={ {n!}\over{ {(n-m)!{m!} } } }$
从n个元素中取出m个的所有组合个数

插板法

n个完全相同元素分k组，每组至少 $a_i$ 个元素，总共多少种分法
插板法公式： $C(n-{\sum a_i}+k-1, n-\sum a_i)$
本质是求 $\sum x_i=n, x_i>=a_i$ 的解的组数
不相邻的排列：n个连续的数中选k个，任意两个数都不相邻的组合有 $C(n-k+1, k)$ 种
应用：求给相同元素分组的方案数或求线性不定方程的解的组数

多重组合数/多重集的排列数

多重集 $S={n_1\cdot a_1,…,n_k\cdot a_k}$ 是指包含重复元素的广义集合
多重组合数/多重集的排列数是指k种球且每种球有多个的这些球的全排列数
$C(n, (n_1, n_2,…,n_k))={ {n!}\over{\prod _{i=1}^k n_i!} }$

多重集的组合数

定义：从多重集中选取 r 个元素组成一个多重集的方案数
等价于 $\sum x_i=r$ 的非负整数解的组数，插板法： $C(r+k-1, r)$
容斥原理： $\sum _{p=0}^k (-1)^p \sum _A C(k+r-1-\sum A n{A_i}-p, k-1)$

部分圆排列公式

$Q_n^r={ {A_n^r}\over{r} }={ {n!}\over{r\times(n-r)!} }$

卢卡斯定理

$C(n, m)modp=C(ceil(n/p), ceil(m/p))C(n modp, m modp)modp$
若p是小于1e5的质数，则其中 $C(n modp, m modp)$ 可直接求
应用：求解大组合数取模问题，解决阶乘无法解决的问题

组合数性质

对称性 $C(n,m)=C(n,n-m)$
定义导出递推式 $C(n, k)={n \over k}C(n-1, k-1)$
递推式 O(n^2) 推导（杨辉三角公式表达） $C(n, m)=C(n-1,m)+C(n-1, m-1)$
二项式定理 $(a+b)^n = {\sum _{i=0}^n C(n, i)a^{n-i}b^i}$
二项式定理特殊情况 $\sum _{i=0}^n C(n, i)=2^n$
组合数拆分公式 $\sum _{i=0}^m C(n, i)C(m, m-i)=C(m+n, m), (n>=m)$

排列数性质

先安排特定位置再安排其余位置 $A_n^m=nA_{n-1}^{m-1}$
递推公式 $A_n^m=A_{n-1}^m+mA_{n-1}^{m-1}$

Cayley公式

n个点的无向完全图的生成树（有标号无根树）计数： $n^{n-2}$
n个点给定度数为 $d_{1-n}$的有标号无根树计数： ${(n-2)!}\over{\prod _{i=1}^n(d_i-1)!}$

应用

计数问题，概率期望

代码

//卢卡斯定理
ll n, m, mod, f[N];
//快速幂
ll qpow(ll a, ll x)
{
    a%=mod;
    ll res=1;
    while(x)
    {
        if(x&1) res=res*a%MOD;
        a=a*a%MOD;
        x>>=1;
    }
    return res;
}
//定义+乘法逆元求组合数，a/b=a*b的乘法逆元
ll C(ll n, ll m)
{
    if(m>n) return 0;
    return (f[n]*qpow(f[m], mod-2)%MOD)*qpow(f[n-m], mod-2)%MOD;
}
//卢卡斯定理
ll lucas(ll n, ll m)
{
    if(!m) return 1;
    return C(n%MOD, m%MOD)*lucas(n/mod, m/mod)%MOD;
}
void solve()
{
    cin>>n>>m>>mod;
    //初始化阶乘
    a[0]=1;
    for(int i=1; i<=p; ++i) a[i]=a[i-1]*i%p;
    cout<<lucas(n+m, m)<<"\n";
}

抽屉原理

定义

n个物体划分k组，至少存在一组，含有大于等于 ceil(n/k) 个物体

应用

证明存在性证明和求最坏情况下的解

容斥原理

定义

设全集U中有n种不同的属性（相同维度下不同状态值），而第i种属性称 $P_i$ ，拥有属性 $P_i$ 的元素构成集合 $S_i$ ，则 $|{\bigcup^{n}{i=1} }{S_i}|={\sum ^{n}{m=1} }(-1)^{m-1}{\sum {a_i<a{i+1} }|{\bigcap^{m}{i=1} }S{a_i}|}$

补集

对于全集U下的集合的并可以使用容斥原理计算，而集合的交则用全集减去补集的交集求得： $|\bigcap {i=1}^n S_i|=|U|-|{\bigcup^{n}{i=1} }\overline{S_i}|$

容斥模型

全集 U：没有限制条件的总答案
元素：最基本的子问题
属性：限制条件在元素中的体现
目标：所有元素满足对应属性时集合的大小
技巧：位运算枚举子集

不定方程非负整数解计数

题意：给定不定方程 $\sum _{i=1}^n x_i=m$ 和 n个限制条件 $x_i<=b_i$ ，求方程的非负整数解个数
容斥模型： $|\bigcap {i=1}^n S_i|=|U|-|{\bigcup^{n}{i=1} }\overline{S_i}|=C(m+n-1, m)-{\sum ^{n}{k=1} }(-1)^{k-1}{\sum {a_i<a{i+1} }C(m-\sum (b{a_i}+1)+k-1, m-\sum ({b_{a_i} }+1))}$

min-max容斥

对满足全序关系且其中元素满足可加减性的序列 ${x_i}$ ，设其长度为n，并设 $S={1,2,3,…,n}$ ，则有奇加偶减
${max}{i \in S}x_i={\sum}{T \subseteq S} (-1)^{|T|-1}{min}_{j \in T} x_j$
${min}{i \in S}x_i={\sum}{T \subseteq S} (-1)^{|T|-1}{max}_{j \in T} x_j$
期望
- $E(max(S))={\sum}_{T \subseteq S}(-1)^{|T|-1}E(min(T))$
- $E(min(T))={1 \over { {\sum}_{i \in T} P_i} }$
应用：假设有S个对象，求把所有东西都取到的期望。通过求子集的期望，然后容斥间接得到结果

应用

解决集合的计数问题

线性代数

矩阵

实现

矩阵结构体，定义乘法运算、快速幂。

思想

矩阵表示线性代数式，通过矩阵快速幂快速计算递推式的结果，重点在求递推式

应用

题目所求为递推式结果，且递推次数较大

代码

const int N=10;
int sz;
struct Matrix{
  int mat[N][N]; //结构体和函数内的int最多开5e5大小，若大小超过，则用全局变量
  Matrix(){memset(mat, 0, sizeof(mat));}//初始化
  Matrix operator*(const Matrix& T) const //矩阵乘法
  {
    Matrix res;
    for(int i=0; i<sz; ++i)
    {
      for(int k=0; k<sz; ++k)
      {
        if(!mat[i][k]) continue;
        for(int j=0; j<sz; ++j)
          res.mat[i][j]+=mat[i][k]*T.mat[k][j], res.mat[i][j]%=MOD;
      }
    }
    return res;
  }
  Matrix qpow(int x) const //矩阵快速幂
  {
    Matrix bas, res;
    for(int i=0; i<sz; ++i) res.mat[i][i]=1;
    for(int i=0; i<sz; ++i)
      for(int j=0; j<sz; ++j)
        bas.mat[i][j]=mat[i][j]%MOD;
    while(x)
    {
      if(x&1) res=res*bas;
      bas=bas*bas;
      x>>=1;
    }
    return res;
  }
};

高斯消元

实现

$O(n^3)$

增广矩阵 $(A|b)$ 行初等行变换为行最简形
还原线性方程组
求解第一个变量
补充自由未知量
列表示方程组通解

思想

线性无关

应用

线性方程组求解： $n \times m$ 增广矩阵
行列式计算： $n \times n$ 矩阵化为对角线矩阵，行列式为对角线之积
矩阵求逆：构造 $n \times 2n$ 矩阵 $(A, I_n)$ ，用高斯消元将其化简为 $(I_n, A^{-1})$ ，若左半部分非单位矩阵，则不可逆
处理有后效性DP

代码

//高斯消元
double M[N][N], ans[N];//增广矩阵、解
bool gauss(int n, int m)
{
    int line=1;//1 to line 行是找到主元的行
    //增广矩阵初等行变换为行最简型
    for(int i=1; i<m; ++i)//枚举第i列考虑无穷解，循环到n
    {
        int r=line;
        for(int j=line+1; j<=n; ++j)//寻找第i列最大的数所在的行
            if(fabs(M[r][i])<fabs(M[j][i]))
                r=j;
        if(fabs(M[r][i])<EPS)//找不到主元
            continue;
        if(line!=r) swap(M[line], M[r]);//交换行
        for(int j=1; j<=n; ++j)//遍历全部行
        {
            if(j==line) continue;
            double mul=M[j][i]/M[line][i];//减去第i列以消元
            for(int k=i; k<=m; ++k)
                M[j][k]-=M[line][k]*mul;
        }
        ++line;//找到主元的行+1
    }
    if(line>n)//唯一解
    {
        //还原线性方程组求解所有变量
        for(int i=n; i>=1; --i)
        {
            ans[i]=M[i][m]/M[i][i];//最终矩阵只有nXn对角线和最后一列不为0
        }
        for(int i=1; i<=n; ++i)
            cout<<fixed<<setprecision(2)<<ans[i]<<"\n";
        return true;//存在唯一解
    }
    else
    {
        while(line<=n)
        {
            if(fabs(M[line++][m]) != 0)//无解
            {
                cout<<"-1\n";
                return false;
            }
        }
        cout<<"0\n";//无穷解
        return false;
    }
}

线性基

实现

线性空间
- 线性包/张成：集合 $T \subseteq S$ ，所有子集 T 的运算 op 组成的集合称集合S的张成/线性包，记作 span(S)。即，在 S 中选出任意多个数，其运算 op 的所有可能结果组成的集合
- 线性相关、线性无关：对集合 S ，若存在一个元素 $S_j$ 使得 S 在除去该元素后得到的集合 $S’$ 的张成 span( $S’$ )中包含 $S_j$ ，即 $S_j \in span(S’)$ ，则称集合 S 线性相关，否则线性无关
- 极大线性无关组：删除多余的可被其他向量表示的向量剩下的最多数量的线性无关向量组
- 向量组的秩：极大线性无关组的大小
线性基
- 集合 B 是集合 S的线性基的充要条件
  - $S \subseteq span(B)$ ，即 S 是 B 的张成的子集
  - B是线性无关的
- 集合 B 中元素的个数称线性基的长度
- 基本性质
  - B 是极小的满足线性基性质的集合
  - S 中的任意元素都可以唯一表示为 B 中若干个元素运算 op 的结果
- 限定向量均在 $Z_2^n$ 下，则为异或线性基，二进制长度为 $[log_2N]$ 的数组 a 描述一个值域为 $[1,N]$ 的线性基
构造异或线性基
- 特殊性质
  - $a_i=0$ 且只有 $a_i$后所有的 $a_j$ 的第i个二进制位可能为1
  - $a_i \neq 0$ 且整个 a 数组只有 $a_i$ 第 i 个二进制位为1， $a_i$ 更高二进制位必为0，更低二进制位可能为1
- 插入：在已存在线性基插入数 t $O(logt)$
  - 逆序枚举 t 的所有为1的二进制位 $j=L\to 0$
    - 若 $a_j \neq 0$ ，则令 $t=t xor a_j$ 消去该位1
    - 若 $a_j = 0$ ，则
      - 枚举 $k \in [0, j)$ ，若 t 的第 k 位为1，则令 $t=txora_k$ 保证该位1不重复
      - 枚举 $k \in (j,L]$ ，若 $a_k$ 的第 j 位为1，则令 $a_k=a_kxort$ 保证该位1不重复
      - 令 $a_j=t$ ，结束插入
- 判断：若插入 x 最后为0，则说明当前线性基可以异或得到数 x
- 合并：将一个线性基的所有元素插入另一个线性基，合并后的线性基为两个集合的并的线性基 $O(log^2t)$
- 查询异或最值
  - 异或最小值：线性基中的最小值
  - 异或最大值：线性基所有元素的异或和
- 查询k小值
  - 枚举 k 所有为1的二进制位，若该位为1，则将线性基中控制的第 i 小的二进制位的元素异或到答案中

思想

异或线性基可以使用异或运算表示原数集使用异或运算能表示的所有数

应用

子集异或一类题目
给定向量组找一组极大线性无关组
对找到的一组极大线性无关组，判断某向量能否被其线性表出
求极大线性无关组的秩
对找到的一组极大线性无关组，求其张成的线性空间中的最大元/最小元

代码

//线性基
int L, acnt;//线性基的秩
ll a[N];
//初始化
void linearbasis(int l) 
{
    L=l;
    acnt=0;
    memset(a, 0, sizeof(a));
}
//插入
bool insert(ll t)
{
    //逆序枚举二进制位
    for(int j=L; j>=0; --j)
    {
        //若t的第j位为0，则跳过
        if(!(t&(1LL<<j))) continue;
        //若a[j]!=0，则用a[j]消去t的第j位上的1
        if(a[j]) t^=a[j];
        else
        {
            //找到可以插入a[j]的位置
            //用a[0, j-1]消去t的第[0,j)位上的1
            for(int k=0; k<j; ++k) 
                if(t&(1LL<<k)) t^=a[k];
            //用t消去a[j+1, L]第j位上的1
            for(int k=j+1; k<=L; ++k) 
                if(a[k]&(1LL<<j)) a[k]^=t;
            //插入到a[j]位置上
            a[j]=t;
            //结束插入
            ++acnt;
            return true;
        }
        // 此时 t 的第 j 位为 0，继续寻找其最高位上的 1
    }
    // 如果没有插入到任何一个位置上，则表明 t 可以由 a 中若干个元素的异或和表示出，即 t 在 span(a) 中
    return false;
}
//查询异或最大值
ll queryMax()
{
    ll res=0;
    for(int i=0; i<=L; ++i) res^=a[i];
    return res;
}
//查询异或第k小值
ll queryKMin(ll k=1)
{
    if(acnt != n) --k;//比较线性基的秩和插入的变量的个数，可能是0
    //若 k 超过所有不同异或和的数量，所有不同的异或和的数量为(1<<线性基的秩)-1
    if(k >= (1LL<<acnt)) return -1;
    ll ans=0;
    for(int i=0; i<=L; ++i)
    {
        if(k & (1LL<<i))
            ans^=a[i];
    }
    return ans;
}

概率与期望

随机变量的数字特征

概率

性质
- 单调性 $A \subset B \to P(A) \leqq P(B)$
- 容斥原理 $P(A+B)=P(A)+P(B)-P(AB)$
- P(A-B)=P(A)-P(AB)

期望

$E(X)={\int}xdF(x)$
F(x)是随机变量X的分布函数，当X离散时为概率P(x)
性质
- 线性性 $E(aX+bY)=aE(X)+bE(Y)$
- 乘积的期望 $E(XY)=EX \times EY$ 充分条件为二者期望存在且相互独立

条件分布与条件期望

已知Y=y的条件下X的期望，记 $E(X|Y=y)$
性质
- 全期望公式 $E(E(X|Y))=E(X)$

方差

$D(X)=E(X-E(X))^2$
性质
- $D(aX+b)=a^2 \times D(X)$
- $D(X)=E(X^2)-E(X)^2$
标准差 $\sigma (X)=\sqrt{D(X)}$

协方差与相关系数

$Cov(X, Y)=E((X-E(X))(Y-E(Y)))$
性质
- $Cov(X, Y)=Cov(Y, X)$
- $Cov(aX+bY, Z)=aCov(X, Z)+bCov(Y, Z)$
- $D(X)=Cov(X, X)$
- $D(X+Y)=D(X)+2Cov(X, Y)+D(Y)$
Pearson相关系数 ${\rho}_{X, Y}={ {Cov(X, Y)}\over{\sigma(X)\sigma(Y)} }$

博弈论

待补充

一	二	三	四	五	六	日
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31