# 常用代码模板 4—— 数学知识

一些常用的整除小知识

（1）能被 8 整除，等价于后 3 位可以被 8 整除。

（2）能被 2 或 5 整除，等价于后 1 位可以被 2 或 5 整除。

（3）能被 4 整除，等价于后 2 位可以被 4 整除。

（4）能被 3 或 9 整除，等价于各位数字之和能被 3 或 9 整除。

（5）能被 11 整除，等价于奇树位各位数字之和减去偶位各位数字之和的差值能被 11 整除。

（6）能被 7 或 11 或 13 整除，等价于后三位之前的数减去后三位的差值可以被 7 或 1 或 13 整除。

（7）一种特殊的判别某数是否能被什么整除方法 —— 截尾法（目前只给出思路，之后编写代码）。

# 思想：截尾法

先看个例子：112024是否为19的倍数？
112024先变为->11202和4，然后进行11202+2*4=11210
然后继续变为->1121和0，然后进行1121+2*0=1121
然后继续变为->112和1，然后进行112+2*1=114
然后继续变为->11和4，然后进行11+2*4=19，19是19的倍数，所以原数是19的倍数。
---前置知识---
a|b，a|c  =>  a|(b±c)
A = 10m + n (m位其他位数的数值，n为个位数字)
B = 10(m + 2n) = 10m + 20n (乘的10对是否是19的倍数没有影响，如果要有影响也要是后面产生的)
C = B - A = 19n
A = B - C (C已经是19的倍数了，如果B也是19的倍数，那么A就是19的倍数)

-----------------------------------------------------------------------------------------
一般性：
首先我们先确定好要是以谁为倍数。
确定好以谁倍数（设为x）之后,对x做乘积，使之满足各位是1或是9。
假设是17，那么合适的值为51。
因为我们要截掉尾巴，所以就是要加上几n或是减掉几n使之没有个位上的值。
A = 10m + n
进行：A - 51n = 10(m - 5n)
这样之后就按 m - 5n 来看是否为17的倍数。

# 试除法判定质数

bool is_prime(int x)
{
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
            return false;
    return true;
}

# 试除法分解质因数

void divide(int x)
{
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        {
            int s = 0;
            while (x % i == 0) x /= i, s ++ ;
            cout << i << ' ' << s << endl;
        }
    if (x > 1) cout << x << ' ' << 1 << endl; // n中最多只包含一个大于sqrt(n)的质因子 
    cout << endl;
}

# 朴素筛法求素数

int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (st[i]) continue;
        primes[cnt ++ ] = i;
        for (int j = i + i; j <= n; j += i)
            st[j] = true;
    }
}

# 线性筛法求素数

// 另一个埃氏筛法的时间复杂度为：O(nlog(lon n))

// 对于任何一个合数都有最小质因子,这种方法求素数的同时也得到了每个数的最小质因子
int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉
// 复杂度为O(n)
void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i; // 未被筛掉的轮到的素数，去筛掉它的倍数
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
			// 确保每个合数，只被最小的质因子筛掉            
            st[primes[j] * i] = true;
            // 1. i % primes[j] != 0，i中的最小质因子都是比primes[j]大，i * primes[j]这个数的最小质因子，就是primes[j]
            // 2. i % primes[j] == 0，primes[j]是i的最小质因子，i *primes[j]的最小质因子
            if (i % primes[j] == 0) break; // 确保是被最小的质因数筛掉
        }
    }
}

# 试除法求所有约数

vector<int> get_divisors(int x)
{
    vector<int> res;
    for (int i = 1; i <= x / i; i ++ )
        if (x % i == 0)
        {
            res.push_back(i);
            if (i != x / i) res.push_back(x / i);
        }
    sort(res.begin(), res.end());
    return res;
}

# 约数个数和约数之和

int范围内，约数最多的数的约束个数差不多为1500个
如果 N = p1^c1 * p2^c2 * ... *pk^ck
约数个数： (c1 + 1) * (c2 + 1) * ... * (ck + 1)
约数之和： (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)

# 欧几里得算法

证明简述:

** 结论：** 对任意非负整数 $a$ 和正整数 $b$ ，有 $\gcd(a,b)=\gcd(b,a \bmod b)$

** 证明：** 因为 $b$ 是正整数，所以 $a=kb+r$ ， $k$ 是整数。 $\therefore a \mod b =a-kb$

设 $d$ 是 $a,b$ 的公因子，即 $d|a,d|b$ ，所以 $d|kb$ 。由 $d|a$ 和 $d|kb$ 得 $d|(a \bmod b)$ ，因此 $d$ 是 $b$ 和 $a \bmod b$ 的公因子。

因此 $a,b$ 的公因子集合与 $b$ ， $a \bmod b$ 的公因子集合相等，两个集合的最大值也相等。证毕。

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

# 求欧拉函数

前置知识

| 互质：互质是公约数只有 1 的两个整数，叫做互质整数。

欧拉函数定义

$1∼N-1$ 中与 N 互质的数的个数被称为欧拉函数，记为 $\phi(N)$ 。
若在算数基本定理中， $N=p_1^{a_1}p_2^{a_2}...p_m^{a_m}$ ，则：
\phi(N)=N\cdot\frac{p_1-1}{p_1}\cdot\frac{p_2-1}{p_2}\cdot...\cdot\frac{p_m-1}

int phi(int x)
{
    int res = x;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        {
            res = res / i * (i - 1);
            while (x % i == 0) x /= i;
        }
    if (x > 1) res = res / x * (x - 1);

    return res;
}

欧拉定理：

定义： 设 $m$ 是正整数， $(a,m)=1$ ，则 $a^{\varphi(m)} \equiv 1\pmod m$

** 证明：** 由定理 D，设 $\{x_1,x_2,…,x_{\varphi(m)}\}$ 是模 $m$ 的一个缩系，则 $\{ax_1,ax_2,…,ax_{\varphi(m)}\}$ 也是模 $m$ 的缩系。

因此 $(ax_1)(ax_2)…(ax_{\varphi(m)}) \equiv x_1x_2…x_{\varphi(m)}\pmod m$

$a^{\varphi(m)}x_1x_2…x_{\varphi(m)} \equiv x_1x_2…x_{\varphi(m)}\pmod m$

又 $\because (x_i,m) = 1,i = 1,2,…,\varphi(m)$

$\therefore a^{\varphi(m)} \equiv 1\pmod m$ 。证毕。

** 意义：** 说明数列 $A_i = a^i\pmod m$ 一定是周期数列，周期最大不可能超过 $\varphi(m)$ 。

当 $m$ 为素数时，由于 $\varphi(m)=m-1$ ，带入欧拉定理可立即得到费马小定理。（ $\varphi(m)$ 指不超过 $m$ 的和 $m$ 互质的数。）

e.g. $2^{\varphi(7)}\equiv 1\pmod 7$ ，这里周期不超过 $\varphi(7)=6$ ，但是 $2^3 \equiv 1\pmod 7$ 。也就是说周期是 $3$ 而非 $6$ 。

费马小定理：

** 定义：**① 设 p 是素数，则对于任意的整数 a，有 $a^p \equiv a\pmod p$ 。② 若 p 是素数，a 是正整数，且 $\gcd(a,p)=1$ ，则 $a^{p-1} \equiv 1 \pmod p$

** 证明：** 使用归纳法证明：显然 $1^p \equiv 1\pmod p$ ，假设 $a^p \equiv a \pmod p$ 成立，那么通过二项式定理有：

$(a+1)^p=a^p+\dbinom{p}{1}a^{p-1}+\dbinom{p}{2}a^{p-2}+…+\dbinom{p}{p-1}a + 1$

因为 $\dbinom{p}{k}=\frac{p(p-1)…(p-k+1)}{k!}$ 对于 $1 \leq k \leq p-1$ 成立，在模 $p$ 意义下， $\dbinom{p}{1}\equiv\dbinom{p}{2}\equiv…\equiv\dbinom{p}{p-1}\equiv 0 \pmod p$ ，那么 $(a+1)^p \equiv a^p + 1\pmod p$ ，将 $a^p\equiv a \pmod p$ 带入得 $(a+1)^p\equiv a+1 \pmod p$ 。证毕。

扩展欧拉定理 $^*$ ：

定义：

a^b \equiv \begin{cases} a^{b \bmod \varphi(m)},&\gcd(a,m)=1,\\ a^b, & \gcd(a,m)\neq 1,b<\varphi(m),\pmod m\\a^{(b \bmod \varphi(m)+\varphi(m))},& \gcd(a,m) \neq 1,b \geq \varphi(m).\end

** 用法解释：** 对于第二行，如果 $b < \varphi(m)$ 的话，就不能降幂了。主要是因为题目中 $m$ 不 hi 太大，而如果 $b < \varphi(m)$ ，自然复杂度是可以接受的。而如果 $b \geq \varphi(m)$ 的话，复杂度可能就超出预期了，这个时候我们才需要降幂来降低复杂度。

证明非常复杂，此处略去了捏。

# 筛法求欧拉函数

int primes[N], cnt;     // primes[]存储所有素数
int euler[N];           // 存储每个数的欧拉函数
bool st[N];         // st[x]存储x是否被筛掉


void get_eulers(int n)
{
    euler[1] = 1;
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i])
        {
            primes[cnt ++ ] = i;
            euler[i] = i - 1;
        }
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            int t = primes[j] * i;
            st[t] = true;
            if (i % primes[j] == 0)
            {
                euler[t] = euler[i] * primes[j];
                break;
            }
            euler[t] = euler[i] * (primes[j] - 1);
        }
    }
}

# 快速幂

使用很频繁，数论常客。
数论很多题目都需要用到long long
求 m^k mod p，时间复杂度 O(logk)。

int qmi(int m, int k, int p)
{
    int res = 1 % p, t = m;
    while (k)
    {
        if (k&1) res = res * t % p;
        t = t * t % p;
        k >>= 1;
    }
    return res;
}

# 扩展欧几里得算法

** 前置知识：** 欧几里得算法（上已证明，此处省略）、裴蜀定理（先礼后兵）。

** 裴蜀定理：** 设 $a,b \in Z$ ， $a \neq 0$ ， $b \neq 0$ ，集合 $A = \{xa+yb\ \ |\ \ x,y\in Z\}$ ， $d$ 为 $A$ 中最小的正整数，则 $(a,b)=d$ 。

证明：

①首先证明 $d$ 的存在性，即集合 $A$ 中一定存在最小正整数。集合 $A$ 中的元素为整数 $a$ 和 $b$ 的整系数线性组合，由于 $1×a +0×b$ 和 $(-1) × a + 0 × b$ 中必有一个正整数，所以集合 $A$ 中至少存在一个正整数。由正整数的良序性，集合 $A$ 中的所有正整数中必然存在一个最小值 $d$ ，不妨设 $d = sa + tb$ ，其中 $s,t \in Z$ 。

②接着证明 $d$ 是 $a$ 和 $b$ 的公因数。已知对于整数 $a$ 和 $d$ ，存在整数 $q$ 和 $r$ 使得 $a = qd +r,0 \leq r < d$ 进而 $r = a - qd = a - q(sa + tb) = (1 - qs)a - qtb$ 。因此 $r\in A $，又因为 $d$ 是 $A$ 中的最小正整数，且有 $0 \leq r < d$ ，所以只能是 $r = 0$ , 于是 $a = qd$ ，即 $d|a$ ，同理可知 $d|b$ 。

③最后证明 $d$ 是 $a$ 和 $b$ 的最大公因数。设 $c$ 是 $a$ 和 $b$ 的任何一个公因数，则 $c|a$ ， $c | b$ ，由于 $d = sa + tb$ ，故由定理 $1$ 可知 $c|d$ ，又因为 $d >0$ ，所以 $d\geq c$ 。证毕。

推论：设 $a,b∈Z$ ，当 $(a,b)=1$ 时，一定存在整数 $s$ 和 $t$ , 使得 $sa+tb = 1$ 。

设 $r_0,r_1 \in Z , r_0 > r_1 > 0$ ，当 $(r_0,r_1) = 1$ 时，假设存在整系数 $s$ 和 $t$ 使得 $sr_0 + tr_1 = 1$ 上述等式两边对 $r_0$ 取模，得到 sr_0 + tr_1 \equiv 1 \, \pmod

即 tr_1 \equiv 1\pmod

因此得到一个重要结论：t \equiv r_1^{-1}\pmod

同理得到：s \equiv r_0^{-1}\pmod

综上：设 $r_0,r_1 \in Z,r_0 > r_1 > 0$ ，当 $(r_0,r_1)=1$ 时， $r_1^{-1}\pmod {r_0}$ 和 $r_0^{-1}\pmod {r_1}$ 一定存在，而且 $r_1^{-1}\pmod {r_0} = t,\ r_0^{-1}\pmod {r_1} = s$ 。 $(r_0,r_1)=1$ 是 $r_1^{-1}\pmod {r_0}$ 和 $r_0^{-1}\pmod {r_1}$ 存在的充要条件。

裴蜀定理给出了求乘法逆元的途径。

// 求x, y，使得ax + by = gcd(a, b)
int exgcd(int a, int b, int &x, int &y)
{
    if (!b)
    {
        x = 1; y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= (a/b) * x;
    return d;
}

# 中国剩余定理

LL exgcd(LL a,LL b,LL &x,LL &y){
    if(!b){
        x=1,y=0; 
        return a;
    }
    LL d=exgcd(b,a%b,y,x);
    y -= (a/b) * x;
    return d;
}
LL CRT(LL m[],LL r[]){
    LL m=1,ans=0;
    for(int i=1;i<=n;i++)M*=m[i];
    for(int i=1;i<=n;i++){
        LL c=M/m[i],x,y;
        exgcd(c,m[i],x,y);
        ans=(ans+r[i]*c*x%M)%M;
    }
    return (ans%M+M)%M;
}

# 高斯消元

具体步骤说明：

以下的 $①$ 到 $④$ 是一个循环操作，每次确定一列的第一位数字是 $1$ ， $⑤$ 是一个单独的循环操作，每次确定每一列上只有对应对角线上的数值是非负的（不考虑最后一列数值列）。

① 找到绝对值当前位对应绝对值最大的一行。

② 将该行换到能换的最上面。

③ 将改行对应的第一个非零值变为 1。

④ 将下面所有行对应的值全部消成 0。

⑤遍历每行后，变为一个上三角矩阵后，从下到上再次进行一定的操作，使之变为只有从左上到右下上有数据的矩阵。这样就方程的解就显而易见了。

// a[N][N]是增广矩阵
int gauss()
{
    int c, r;
    for (c = 0, r = 0; c < n; c ++ )
    {
        int t = r;
        for (int i = r; i < n; i ++ )   // 找到绝对值最大的行
            if (fabs(a[i][c]) > fabs(a[t][c]))
                t = i;

        if (fabs(a[t][c]) < eps) continue;

        for (int i = c; i <= n; i ++ ) swap(a[t][i], a[r][i]);      // 将绝对值最大的行换到最顶端
        for (int i = n; i >= c; i -- ) a[r][i] /= a[r][c];      // 将当前行的首位变成1，一定要倒着进行。如何正着开始，第一个就会之间变为1，导致后面除的都是1。
        for (int i = r + 1; i < n; i ++ )       // 用当前行将下面所有的列消成0
            if (fabs(a[i][c]) > eps) // 浮点数存储0的时候会有精度问题，需要大于一个很小的数判断是否是0
                for (int j = n; j >= c; j -- )
                    a[i][j] -= a[r][j] * a[i][c];

        r ++ ;
    }

    if (r < n)
    {
        for (int i = r; i < n; i ++ )
            if (fabs(a[i][n]) > eps)
                return 2; // 无解
        return 1; // 有无穷多组解
    }

    for (int i = n - 1; i >= 0; i -- )
        for (int j = i + 1; j < n; j ++ )
            a[i][n] -= a[i][j] * a[j][n];

    return 0; // 有唯一解
}

# 递推法求组合数

参考范围：题目的数据有 10 万组，询问的 ab 的范围为： $1 \leq b \leq a \leq 2000$ ，以下方式处理复杂度： $n^2$ 。

// c[a][b] 表示从a个苹果中选b个的方案数
for (int i = 0; i < N; i ++ )
    for (int j = 0; j <= i; j ++ )
        if (!j) c[i][j] = 1;
        else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;

# 通过预处理逆元的方式求组合数

参考范围：题目的数据有 1 万组，询问 ab 的范围为： $1 \leq b \leq a \leq 10^5$ ，以下方式处理复杂度： $n \log n$ 。

此处要采用逆元，逆元的定义为：如果一个线性同余方程 $ax\equiv 1\pmod b$ ，则称 $x$ 为 $a \bmod b$ 的逆元，记作 $a^{-1}$ 。

// 首先预处理出所有阶乘取模的余数fact[N]，以及所有阶乘取模的逆元infact[N]
// 如果取模的数是质数，可以用费马小定理求逆元
int qmi(int a, int k, int p)    // 快速幂模板
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}

// 预处理阶乘的余数和阶乘逆元的余数
fact[0] = infact[0] = 1;
for (int i = 1; i < N; i ++ )
{
    fact[i] = (LL)fact[i - 1] * i % mod;
    infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
}

# Lucas 定理

参考范围：题目的数据有 20 组，询问 ab 的范围为： $1 \leq b \leq a \leq 10^{18}$ ，但是 $1\leq p\leq 10^5$ ，采用以下方法处理后时间复杂度变为： $p\log n\log p$ 。

其公式为： $C^{b}_{a} \equiv C^{b \bmod p}_{a \bmod p} * C^{b/p}_{a/p} \pmod p$

** 证明：** 考虑 $\dbinom{p}{n} \bmod p$ 的取值，注意到 $\dbinom{p}{n} = \frac{p!}{n!(p-n)!}$ ，分子的质因子分解中 $p$ 的次数恰好为 1，因此只有当 $n=0$ 或 $n=p$ 的时候 $n!(p-n)!$ 的质因子分解中含有 $p$ ，因此 \dbinom{p}{n} \bmod p=[n = 0 \or n=p]。进而我们可以得出

(a+b)^p = \sum\limits_{n=0}^p\dbinom{p}{n} a^nb^{p-n}\equiv \sum\limits_{n=0}^p[n=0\or n=p]a^nb^{n-p}\equiv a^p +b^p \pmod p

注意过程中没有用到费马小定理，因此这一推导不仅适用于整数，亦适用于多项式。因此我们可以考虑二项式 $f^p(x)=(ax^n + bx^m)^p \bmod p$ 的结果

$(ax^n + bx^m)^p \equiv a^p x^{pn} + b^px^{pm} \equiv ax^{pn}+bx^{pm}\equiv f(x^p)$

考虑二次式 $(1+x)^n \bmod p$ ，那么 $\dbinom{n}{m}$ 就是求其在 $x^m$ 次项的取值。使用上述引理，我们可以得到：

(1+x)^n \equiv (1+x)^{p\lfloor n/p \rfloor}(1+x)^{n \bmod p} \equiv (1+x^p)^{\lfloor n/p \rfloor}(1+x)^

注意：前者只有在 $p$ 的倍数位置才有取值，而后者最高次项为 $n \bmod p \leq p -1 $，因此这两部分的卷积在任何一个位置只有最多一种方式贡献取值，即在前者部分取 $p$ 的倍数次项，后者部分取剩余项，即 $\dbinom{n}{m} \bmod p = \dbinom{\lfloor n/p \rfloor}{\lfloor m/p \rfloor} * \dbinom{n \bmod p}{m \bmod p} \bmod p$

若p是质数，则对于任意整数 1 <= m <= n，有：
    C(n, m) = C(n % p, m % p) * C(n / p, m / p) (mod p) 
    
int qmi(int a, int k, int p)  // 快速幂模板
{
    int res = 1 % p;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}

int C(int a, int b, int p)  // 通过定理求组合数C(a, b)
{
    if (a < b) return 0;

    LL x = 1, y = 1;  // x是分子，y是分母
    for (int i = a, j = 1; j <= b; i --, j ++ )
    {
        x = (LL)x * i % p;
        y = (LL) y * j % p;
    }

    return x * (LL)qmi(y, p - 2, p) % p;
}

int lucas(LL a, LL b, int p)
{
    if (a < p && b < p) return C(a, b, p);
    return (LL)C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}

# 分解质因数法求组合数

高精度给他算出一个极大的组合数。可以之间按照定义来计算。但是按定义写会运行效率比较低且难写，一般是将之转为 $C_a^b$ 的分解质因数，这样就只要实现一个高精度乘法即可。

当我们需要求出组合数的真实值，而非对某个数的余数时，分解质因数的方式比较好用：
    1. 筛法求出范围内的所有质数
    2. 通过 C(a, b) = a! / b! / (a - b)! 这个公式求出每个质因子的次数。 n! 中p的次数是 n / p + n / p^2 + n / p^3 + ...
    3. 用高精度乘法将所有质因子相乘

int primes[N], cnt;     // 存储所有质数
int sum[N];     // 存储每个质数的次数
bool st[N];     // 存储每个数是否已被筛掉


void get_primes(int n)      // 线性筛法求素数
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}


int get(int n, int p)       // 求n！中的次数
{
    int res = 0;
    while (n)
    {
        res += n / p;
        n /= p;
    }
    return res;
}


vector<int> mul(vector<int> a, int b)       // 高精度乘低精度模板
{
    vector<int> c;
    int t = 0;
    for (int i = 0; i < a.size(); i ++ )
    {
        t += a[i] * b;
        c.push_back(t % 10);
        t /= 10;
    }

    while (t)
    {
        c.push_back(t % 10);
        t /= 10;
    }

    return c;
}

get_primes(a);  // 预处理范围内的所有质数

for (int i = 0; i < cnt; i ++ )     // 求每个质因数的次数
{
    int p = primes[i];
    sum[i] = get(a, p) - get(b, p) - get(a - b, p);
}

vector<int> res;
res.push_back(1);

for (int i = 0; i < cnt; i ++ )     // 用高精度乘法将所有质因子相乘
    for (int j = 0; j < sum[i]; j ++ )
        res = mul(res, primes[i]);

# 卡特兰数

1
2

给定n个0和n个1，它们按照某种顺序排成长度为2n的序列，满足任意前缀中0的个数都不少于1的个数的序列的数量为： Cat(n) = C(2n, n) / (n + 1)
很多方案数都是卡特兰数。

# 容斥原理

** 定义：** 设 $U$ 种元素有 n 种不同的属性，而第 $i$ 种属性称为 $P_i$ ，拥有属性 $P_i$ 的元素构成集合 $S_i$ ，那么

$\left\vert \bigcup\limits_{i=1}^n S_i\right\vert = \sum\limits_i|S_i|-\sum\limits_{i<j}|S_i\cap S_j|+\sum\limits_{i<j<k}|S_i\cap S_j \cap S_k|-\dots\\+(-1)^{m-1} \sum\limits_{a_i<a_{i+1}}\left\vert\bigcap\limits_{i=1}^m S_{a_i}\right\vert+\dots+(-1)^{n-1}|S_1\cap \dots \cap S_n|$

即

$\large\left\vert\bigcup\limits_{i=1}^n S_i\right\vert=\sum\limits_{m=1}^n(-1)^{m-1}\sum\limits_{a_i < a_{i+1}}\left\vert\bigcap\limits_{i=1}^m S_{a_i}\right\vert$

** 证明：** 采用二项式定理

1	枚举所有的情况一种方便的方式就是采用位运算来实现。

# NIM 游戏

** 证明：** 为了证明代码段的定理，只需要证明下面三个定理：

定理 1：没有后继状态的状态是必败状态。

定理 2：对于 $a_1\oplus a_2 \dots\oplus a_n\neq 0$ 的局面，一定存在某种移动使得 $a_1\oplus a_2\oplus\dots\oplus a_n = 0$ 。

定理 3：对于 $a_1\oplus a_2\oplus\dots\oplus a_n = 0$ 的局面，一定不存在某种移动使得 $a_1\oplus a_2\oplus\dots\oplus a_n = 0$ 。

对于定理 1，没有后继状态的状态只有一个，即全 $0$ 局面。此时 $a_1\oplus a_2\oplus\dots\oplus a_n = 0$ 。

对于定理 2，不妨假设 $a_1\oplus a_2\oplus\dots\oplus a_n \neq 0$ 。如果我们要将 $a_i$ 改为 $a_i'$ ，则 $a_i'=a_i\oplus k$ 。（毕竟异或最后的结果非 0，必定存在一个 $a_i$ ，使得 $ 0<a_i’<a_i\oplus k$）

对于定理 3，如果我们要将 $a_i$ 改为 $a_i'$ ，则根据异或运算律可以得出 $a_i=a_i'$ （假设变换后异或仍为 $0$ ，然后两个 $0$ 的式子异或一起结果还是 $0$ ，两两配对异或消除会剩下 $a_i \oplus a_i' = 0$ ，这样只能两个相等了，显然矛盾捏），因而这不是个合法的移动。

给定N堆物品，第i堆物品有Ai个。两名玩家轮流行动，每次可以任选一堆，取走任意多个物品，可把一堆取光，但不能不取。取走最后一件物品者获胜。两人都采取最优策略，问先手是否必胜。

我们把这种游戏称为NIM博弈。把游戏过程中面临的状态称为局面。整局游戏第一个行动的称为先手，第二个行动的称为后手。若在某一局面下无论采取何种行动，都会输掉游戏，则称该局面必败。
所谓采取最优策略是指，若在某一局面下存在某种行动，使得行动后对面面临必败局面，则优先采取该行动。同时，这样的局面被称为必胜。我们讨论的博弈问题一般都只考虑理想情况，即两人均无失误，都采取最优策略行动时游戏的结果。
NIM博弈不存在平局，只有先手必胜和先手必败两种情况。

定理： NIM博弈先手必胜，当且仅当 A1 ^ A2 ^ … ^ An != 0

# 公平组合游戏 ICG

若一个游戏满足：
	1.由两名玩家交替行动；
	2.在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关；
	3.不能行动的玩家判负；
则称该游戏为一个公平组合游戏。
NIM博弈属于公平组合游戏，但城建的棋类游戏，比如围棋，就不是公平组合游戏。因为围棋交战双方分别只能落黑子和白子，胜负判定也比较复杂，不满足条件2和条件3。

# 有向图游戏

SG 定理（适用于任何公平的两人游戏，常被用于决定游戏的输赢结果）：

对于状态 $x$ 和它的所有 $k$ 个后继状态 $y_1,y_2,\dots,y_k$ ，定义 $SG$ 函数：

SG(x)=\operatorname{mex}\

而对于由 $n$ 个有向图游戏组成的组合游戏，设它们的起点分别为 $s_1,s_2,\dots,s_n$ ，则有定理：当且仅当 $SG(s_1) \oplus SG(s_2) \oplus \dots \oplus SG(s_n) \neq 0$ 时，这个游戏是先手必胜的。同时，这是这一个组合游戏的游戏状态 $x$ 的 SG 值。

证明：

数学归纳法。

我们假设对于游戏状态 $x'$ ，其当前节点 $s_1',s_2',\dots,s_n'$ （对于任意 $i$ 有 $s_i'<s_i$ )，皆满足 SG 定理。

显然当 $SG(s_1)' = SG(s_2)'=\dots=SG(s_n)'=0$ 时，该状态能满足 SG 定理。

那么只需要证明对于游戏状态 $x$ ，其当前节点 $s_1',s_2',\dots,s_n'$ 符合 SG 定理，SG 定理便成立。

事实上这一个状态可以看作一个 Nim 游戏，对于某个节点 $s_i$ ，它可以移动到任意一个 SG 值比它小或比它大的节点。

在有向图游戏中，当一方将某一节点 $s_i$ 移动到 SG 值比它大的节点时，另一方可以移动回和 SG 值和 $\operatorname{SG}(s_i)$ 一样的节点，所以向 SG 值较大节点移动是无效操作。

当移动到 SG 值较小的节点时，情况则会和 Nim 游戏一样，能够到达任何一个游戏状态 $x'$ 使得 $SG(x')=SG(s_1'\oplus s_2'\oplus \dots\oplus SG(s_n')<SG(X))$ （注意到前文已经假设 $x'$ 满足 SG 定理），但到达不了 SG 值为 $SG(s_1)\oplus SG(s_2)\oplus \dots\oplus SG(s_n)$ 的节点。

所以状态 $x$ 符合 SG 定理。

1
2
3

给定一个有向无环图，图中有一个唯一的起点，在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动，每次可以移动一步，无法移动者判负。该游戏被称为有向图游戏。
任何一个公平组合游戏都可以转化为有向图游戏。具体方法是，把每个局面看成图中的一个节点，并且从每个局面向沿着合法行动能够到达的下一个局面连有向边。
这个游戏取胜采用了SG定理。

# Mex 运算

1
2
3

设S表示一个非负整数集合。定义mex(S)为求出不属于集合S的最小非负整数的运算，即：
mex(S) = min{x}, x属于自然数，且x不属于S
例如 mex({0,2,4}) = 1, mex({1,2}) = 0。

# SG 函数

1
2
3

在有向图游戏中，对于每个节点x，设从x出发共有k条有向边，分别到达节点y1, y2, …, yk，定义SG(x)为x的后继节点y1, y2, …, yk 的SG函数值构成的集合再执行mex(S)运算的结果，即：
SG(x) = mex({SG(y1), SG(y2), …, SG(yk)})
特别地，整个有向图游戏G的SG函数值被定义为有向图游戏起点s的SG函数值，即SG(G) = SG(s)。

# 有向图游戏的和

设G1, G2, …, Gm 是m个有向图游戏。定义有向图游戏G，它的行动规则是任选某个有向图游戏Gi，并在Gi上行动一步。G被称为有向图游戏G1, G2, …, Gm的和。
有向图游戏的和的SG函数值等于它包含的各个子游戏SG函数值的异或和，即：
SG(G) = SG(G1) ^ SG(G2) ^ … ^ SG(Gm)
    
定理：
    有向图游戏的某个局面必胜，当且仅当该局面对应节点的SG函数值大于0。
	有向图游戏的某个局面必败，当且仅当该局面对应节点的SG函数值等于0。