算法笔记7

2024/4/18 算法快速幂质数约数欧拉函数扩展欧几里得算法中国剩余定理高斯消元求组合数容斥原理博弈论

第四讲数学知识

1. 质数

质数: 大于1，比如：2, 3, 5, 7, 11......等只含有1和本身，这两个约数

acwing 866. 试除法判定质数 https://www.acwing.com/problem/content/868/

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            if (isPrime(x)) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }
        sc.close();
    }
    public static boolean isPrime(int x) {
        if (x < 2) {
            return false;
        }
        int sqrt = (int)Math.pow(x, 0.5);
        for (int i = 2; i <= sqrt; i++) {
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    }
}

acwing 867. 分解质因数 https://www.acwing.com/problem/content/description/869/

从2开始从小到大除，保证了输出的一定是质数

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            getFactor(x);
            System.out.println();
        }
        sc.close();
    }
    public static void getFactor(int x) {
        
        int sqrt = (int)Math.pow(x, 0.5);
        for (int i = 2; x > 1 && i <= sqrt; i++) {
            int cnt = 0;
            while (x % i == 0) {
                x /= i;
                cnt++;
            }
            if (cnt > 0) {
                System.out.println(i + " " + cnt);
            }
        }
        if (x > 1) {
            //输出大于sqrt的因子
            System.out.println(x + " " + 1);
        }
    }
}

acwing 868. 筛质数 https://www.acwing.com/problem/content/870/

埃氏筛法：

筛掉所有质数的倍数

时间复杂度：O（nloglogn）一般可以看成O(n)

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int res = 0;
        //false是质数，true不是质数
        boolean[] flag = new boolean[n +  1];
        for (int i = 2; i <= n; i++) {
            if (!flag[i]) {
                res++;
                for (int j = 2; j * i <= n; j++)  {
                    flag[j * i] = true;
                }
            }
        }
        System.out.println(res);
        sc.close();
    }
}

线性筛法（欧拉筛法）：

思想仍然是排除法

核心：每个合数一定会被其最小质因子筛掉，且只筛一次

记录下当前的质数，从小到大遍历，排除后面的合数，适当的时机停下来，保证只筛一次

为什么保证一定是最小质因子？

答：分为以下两种情况：（prime[j] 简称为pj）

i % pj == 0 pj一定是i的最小质因子，pj一定是pj * i的最小质因子
i % pj != 0 pj一定小于i的所有质因子，pj也一定是pj * i的最小质因子

时线性筛比埃氏筛快约1倍

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int res = 0;
        boolean[] flag = new boolean[n +  1];
        int[] prime = new int[n + 1];
        int cnt = 0;
        
        for (int i = 2; i <= n; i++) {
            if (!flag[i]) {
                prime[cnt++] = i;
            }
            //判断条件不用加j < cnt，原因如下：
            //1. i若为合数，就一定会被前面存下来的i的最小质因数停下来
            //2. i若为质数，因为把i添加到了prime最后，所以一定会执行break
            for (int j = 0; prime[j] * i <= n; j++)  {
                flag[prime[j] * i] = true;
                //prime[j]一定是i的最小质因子
                if (i % prime[j] == 0) {
                    break;
                }
            }
        }
        System.out.println(cnt);
        sc.close();
    }
}

2. 约数

和因数差不多，针对整数

acwing 869. 试除法求约数 https://www.acwing.com/problem/content/871/

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            getFactor(x);
            System.out.println();
        }
        
        sc.close();
    }
    
    public static void getFactor(int x) {
        int sqrt = (int) Math.sqrt(x);
        List<Integer> res = new ArrayList<>();
        for (int i = 1; i <= sqrt; i++) {
            if (x % i == 0) {
                res.add(i);
                if (i != x / i) {
                    res.add(x / i);
                }
            }
        }
        Collections.sort(res);
        for (int i : res) {
            System.out.print(i + " ");
        }
    }
    
}

acwing 870. 约数个数 https://www.acwing.com/problem/content/872/

目的：求N的约数个数

N可以写成以下质因数乘积的形式：（P为质因数）

N中的任意一个约数d，也可以这样展开：

那么只要βi序列的取值不一样，d就不一样

有种取法

故，N的约数个数 =

import java.util.*;

class Main {
    static Map<Integer, Integer> map;
    static final int MOD = 1000000007;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            addCnt(x);
        }
        //必须long
        long res = 1;
        for (Integer i : map.values()) {
            res *= i + 1;
            res %= MOD;
        }
        System.out.println(res);
        sc.close();
    }
    
    public static void addCnt(int x) {
        if (x < 2) {
            return;
        }
        int sqrt = (int) Math.sqrt(x);
        for (int i = 2; x > 1 && i <= sqrt; i++) {
            while (x % i == 0) {
                x /= i;
                map.put(i, map.getOrDefault(i, 0) + 1);
            }
        }
        if (x > 1) {
            map.put(x, map.getOrDefault(x, 0) + 1);
        }
    }
}

acwing 871. 约数之和 https://www.acwing.com/problem/content/873/

目的：求N的约数之和

N可以写成以下质因数乘积的形式：（P为质因数）

N中的任意一个约数d，也可以这样展开：

则有：

sum最后展开就是一堆相加，通过选择不同的指数决定a、b...z取什么（能够列出所有的约数可能）

比如a、b...z全取0，就是1

a、b...z全取，就是N

计算该公式时，使用秦九韶算法计算多项式

比如可以看成

import java.util.*;

class Main {
    static Map<Integer, Integer> map;
    static final int MOD = 1000000007;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            addCnt(x);
        }
        long res = 1;
        for (Integer k : map.keySet()) {
            long v = map.get(k);
            long t = 1;
            for (int i = 0; i < v; i++) {
                //这里是可以取模的，因为不影响结果
                t = (t * k + 1) % MOD;
            }
            res = res * t % MOD;
        }
        System.out.println(res);
        sc.close();
    }
    
    public static void addCnt(int x) {
        if (x < 2) {
            return;
        }
        int sqrt = (int) Math.sqrt(x);
        for (int i = 2; x > 1 && i <= sqrt; i++) {
            while (x % i == 0) {
                x /= i;
                map.put(i, map.getOrDefault(i, 0) + 1);
            }
        }
        if (x > 1) {
            map.put(x, map.getOrDefault(x, 0) + 1);
        }
    }
}

acwing 872. 最大公约数 https://www.acwing.com/problem/content/874/

欧几里得算法

import java.util.*;

class Main {
    
    public static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            int a = sc.nextInt(), b = sc.nextInt();
            System.out.println(gcd(a, b));
        }
        sc.close();
    }
}

3. 欧拉函数

这里为了代码实现，需要转换成这样

求欧拉函数时间复杂度差不多O()

acwing 873. 欧拉函数 https://www.acwing.com/problem/content/875/

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            System.out.println(getEuler(x));
        }
        sc.close();
    }
    
    public static int getEuler(int x) {
        int res = x;
        int sqrt = (int) Math.sqrt(x);
        for (int i = 2; x > 1 && i <= sqrt; 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;
    }

}

acwing 874. 筛法求欧拉函数 https://www.acwing.com/problem/content/876/

首先，只与质因子本身有关，与其个数无关

这里利用线性筛（欧拉筛）法，通过之间的关系，递推求得（质数直接得到，合数递推）

当i为质数时，

当i为合数时，如下所示: （prime[j]简称为pj）

i % pj == 0时，pj是 i 的质因子，和的质因子组成（）相同
- 所以
i % pj != 0时，pj不是 i 的质因子，比的质因子组成多一个
- 所以

import java.util.*;

class Main {
    
    static int[] prime;
    static boolean[] flag;
    static int cnt;
    static int[] phi;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        prime = new int[n];
        phi = new int[n + 1];
        flag = new boolean[n + 1];
        
        System.out.println(getEulerSum(n));
        
        sc.close();
    }
    
    public static long getEulerSum(int x) {
        phi[1] = 1;
        cnt = 0;
        for (int i = 2; i <= x; i++) {
            if (!flag[i]) {
                prime[cnt++] = i;
                phi[i] = i - 1;
            }
            for (int j = 0; i * prime[j] <= x; j++) {
                flag[i * prime[j]] = true;
                if (i % prime[j] == 0) {
                    phi[i * prime[j]] = prime[j] * phi[i];
                    break;
                } else {
                    phi[i * prime[j]] = (prime[j] - 1) * phi[i];
                }
            }
        }
        long res = 0;
        for (int i = 1; i <= x; i++) {
            res += phi[i];
        }
        return res;
    }

}

4. 快速幂

欧拉定理:

当 $，且$ 时，有以下公式：

当p为质数时，就是费马小定理

故有，

acwing 875. 快速幂 https://www.acwing.com/problem/content/877/

import java.util.*;

class Main {
    static int P;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        for(int i = 0; i < n; i++) {
            int a = sc.nextInt(), b = sc.nextInt();
            P = sc.nextInt();
            System.out.println(fastpow(a, b));
        }
        
        sc.close();
    }
    public static long fastpow(long a, long b) {
        if (b == 1) {
            return a;
        }
        long t = fastpow(a, b / 2);
        long res = t * t % P;
        if (b % 2 == 0) {
            return res;
        }
        return res * a % P;
    }
}

import java.util.*;

class Main {
    static int P;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        for(int i = 0; i < n; i++) {
            int a = sc.nextInt(), b = sc.nextInt();
            P = sc.nextInt();
            System.out.println(fastpow(a, b));
        }
        
        sc.close();
    }
    public static long fastpow(long a, long b) {
        long res = 1;
        while (b != 0) {
            if (b % 2 == 1) {
                res = res * a % P;
            }
            a = a * a % P;
            b >>= 1;
        }
        
        return res;
    }
}

acwing 876. 快速幂求逆元 https://www.acwing.com/problem/content/878/

费马小定理：

由此可得逆元为

a与P互质时，一定存在逆元（∈1 ~ P-1）

注意：不能逆元=0判断，因为P=2时， = 1

import java.util.*;

class Main {
    static int P;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        for(int i = 0; i < n; i++) {
            int a = sc.nextInt();
            P = sc.nextInt();
            long res = fastpow(a, P - 2);
            System.out.println(gcd(a, P) == 1 ? res : "impossible");
        }
        
        sc.close();
    }
    public static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
    public static long fastpow(long a, long b) {
        long res = 1;
        while (b != 0) {
            if (b % 2 == 1) {
                res = res * a % P;
            }
            a = a * a % P;
            b >>= 1;
        }
        
        return res;
    }
}

5. 扩展欧几里得算法

acwing 877. 扩展欧几里得算法 https://www.acwing.com/problem/content/879/

求解方程 ax+by = gcd(a, b) 的特解

用b 换 a，用a % b 换 b

然后变形成

对应相等，即可获得答案

import java.util.*;

class Main {
    static long x;
    static long y;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            int a = sc.nextInt(), b = sc.nextInt();
            exgcd(a, b);
            System.out.println(x + " " + y);
        }
        sc.close();
    }
    
    public static long exgcd(long a, long b) {
        if (b == 0) {
            x = 1;
            y = 0;
            return a;
        }
        long res = exgcd(b, a % b);
        long t = x;
        x = y;
        y = t - a / b * y;
        return res;
    }
}

acwing 878. 线性同余方程 https://www.acwing.com/problem/content/880/

$已知求满足的$

如果b = 1，则可用以求解逆元x（只需要 $和$ 互质）而前面的费马小定理还需要p为质数

可转换成求解方程 ax+by = c 的特解 $，$

首先，求解方程 ax+by = gcd(a, b) 的特解： $，$

然后等式两边同时乘以，也就变成了ax+by = c 的特解

也即

import java.util.*;

class Main {
    static long x;
    static long y;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            int a = sc.nextInt(), b = sc.nextInt(), m = sc.nextInt();
            // -m也能过
            long t = exgcd(a, m);
            if (b % t == 0) {
                System.out.println((b / t * x) % m);
            } else {
                System.out.println("impossible");
            }
            
        }
        sc.close();
    }
    
    public static long exgcd(long a, long b) {
        if (b == 0) {
            x = 1;
            y = 0;
            return a;
        }
        long res = exgcd(b, a % b);
        long t = x;
        x = y;
        y = t - a / b * y;
        return res;
    }
}

已知特解 $，$ ，求通解：（详解见算法笔记3）

1.对于：ax+by = gcd(a, b)

构造：

则有：

正负号无所谓

2.对于：ax+by = c gcd(a, b) | c

在前面的基础上，等式两边同时乘以

因为一定是整数，所以可以被k吸收了，整体用t表示，转换成如下式子：

6. 中国剩余定理

两两互质

设

$表示模的逆$

因为两两互质，所以与（其他所有与互质的数的乘积）互质

为什么存在？

因为，由扩展欧几里得算法（）可求逆元（满足条件 $和$ 互质）

（这里不能用费马小定理，因为p不一定是质数！！！）

则

比如验证：

上面等式两边同时对取余

右边都包含有，所以取余后等于0

剩下的，其中在模下等于1，所以剩下

满足

同理，对其他也适用。

acwing 204. 表达整数的奇怪方式 https://www.acwing.com/problem/content/206/

这道题没有两两互质的条件，不是中国剩余定理，而是扩展中国剩余定理

解法：两两式子合并成一个式子（通过构造方程，用扩展欧几里得求出通解，代换回其中一个式子，发现同样可以看成一个类似的新式子，且同时满足那两个式子），合并n - 1次

最后只剩下一个式子后：

为了求出满足其的最小正整数x

只需要：( % + ) % （前提 > 0）

因此，需要对求绝对值（如果前面求exgcd时代入得是而不是的话，好像就不会出现为负数）

注意：求出通解后，必须变到最小正整数，不然会爆long

import java.util.*;

class Main {
    
    static long x, y;
    static long a1, m1, a2, m2;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        a1 = sc.nextLong();
        m1 = sc.nextLong();
        
        for (int i = 0; i < n - 1; i++) {
            a2 = sc.nextLong();
            m2 = sc.nextLong();
            boolean flag = merge();
            if (!flag) {
                return;
            }
        }
        //防止a1为负数
        a1 = Math.abs(a1);
        System.out.println((m1 % a1 + a1) % a1);
        sc.close();
    }
    
    private static boolean merge() {
        long gcd = exgcd(a1, -a2);
        if ((m2 - m1) % gcd != 0) {
            System.out.println(-1);
            return false;
        }
        long x0 = (m2 - m1) / gcd * x;
        long mod = a2 / gcd;
        //把通解变成最小正整数（防止爆long）
        x0 = (x0 % mod + mod) % mod;
        
        long t = a1;
        a1 = a1 / gcd * a2;
        m1 = t * x0 + m1;
        return true;
    }
    
    private static long exgcd(long a, long b) {
        if (b == 0) {
            x = 1;
            y = 0;
            return a;
        }
        long res = exgcd(b, a % b);
        long t = x;
        x = y;
        y = t - a / b * y;
        return res;
    }
    
}

7. 高斯消元

枚举每一列

找到绝对值最大的一行
将该行换到最上面（除去【已固定的行】意义下的最上面）
将该行第一个数变成1
将下面所有行的第c列消成0

再向上消去非零数，只留下每一行的第一个数1，其他消成0（枚举每一行，将前面所有行对应位置消成0）

最终三种情况：①有唯一解（完美阶梯形，增广矩阵满秩）②有无穷多组解（0 = 0，有的方程无意义）③无解（0 = 非0，矛盾）

acwing 883. 高斯消元解线性方程组 https://www.acwing.com/problem/content/885/

注意：浮点数判断是否为0，需要绝对值小于一个eps（比如1e-6）

import java.util.*;

class Main {
    static double[][] g;
    static int n;
    static double eps = 1e-6;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        g = new double[n + 1][n + 2];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n + 1; j++) {
                g[i][j] = sc.nextDouble();
            }
        }
        int res = gauss();
        if (res == 0) {
            for (int i = 1; i <= n; i++) {
                System.out.printf("%.2f\n", g[i][n + 1]);
            }
        } else if (res == 1) {
            System.out.println("Infinite group solutions");
        } else {
            System.out.println("No solution");
        }
        sc.close();
    }
    
    private static int gauss() {
        int row = 1;
        for (int col = 1; col <= n; col++) {
            //找到绝对值最大的一行
            int pos = -1;
            for (int i = row; i <= n; i++) {
                if (pos == -1 || Math.abs(g[pos][col]) < Math.abs(g[i][col])) {
                    pos = i;
                }
            }
            //将该行换到最上面
            swap(pos, row);
            //将该行第一个数变成1
            double t = g[row][col];
            if (Math.abs(t) < eps) {
                //绝对值最大是0
                continue;
            }
            for (int i = 1; i <= n + 1; i++) {
                g[row][i] /= t;
            }
            //将下面所有行的第c列消成0
            for (int i = row + 1; i <= n; i++) {
                double tmp = -g[i][col];
                addRow(row, i, tmp);
            }
            row++;
        }
        //如果上面没执行continue，row就会加n次，等于n+1
        if (row < n + 1) {
            //从row行开始（及以下的行都是0，判断右边的数（第n+1列）是否为0）
            for (int i = row; i <= n; i++) {
                //只要存在 00000 5这样的 0 = 非零数，就是无解
                if (Math.abs(g[i][n + 1]) > eps) {
                    return 2;
                }
            }
            //全是00000 0这种（方程相当于0 = 0），就是有无穷多组解
            return 1;
        }
        //把 上三角 变成0，也可以只对第n+1列的数进行乘积（这里为了代码简便，直接对行进行操作）
        for (int i = n; i >= 2; i--) {
            //从下到上，把上三角的每一列逐步变0
            for (int j = i - 1; j >= 1; j--) {
                double tmp = -g[j][i];
                addRow(i, j, tmp);
            }
        }
        //有唯一解
        return 0;
    }
    //一行row1乘以一个数c加到另一行row2上
    private static void addRow(int row1, int row2, double c) {
        for (int j = 1; j <= n + 1; j++) {
            g[row2][j] += g[row1][j] * c;
        }
    }
    //交换两行
    private static void swap(int a, int b) {
        double[] tmp = g[a];
        g[a] = g[b];
        g[b] = tmp;
    }
}

acwing 884. 高斯消元解异或线性方程组 https://www.acwing.com/problem/content/description/886/

和前面类似（而且更加简单）

关键是：由于是异或，所以在消去时，是这一行的每个元素，和要消去的行的每个元素，对应进行异或

比如：

^ ^ 0 = 0

0 ^ ^ = 1

对应系数就是：

1 1 0 0

0 1 1 1

第一行对应异或第二行

第二行变为：1 0 1 1

即： ^ = 1（与前面相符，因为前面和同号，和异号，所以和也异号）

为什么能这样？

因为，这相当于第一行和第二行，等式左边进行异或，右边进行异或

比如前面这个就是：( ^ ^ ) ^ ( ^ ^ ) = 0 ^ 1 = 1

该等式左边交换顺序，并对应下标相结合后，变成：( ^ 0) ^ ( ^ ) ^ (0 ^ ) = 1

也即 ^ = 1

只看前面系数，就和前面的结论一样了

因此该初等变换成立

import java.util.*;

class Main {
    static int[][] g;
    static int n;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        g = new int[n + 1][n + 2];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n + 1; j++) {
                g[i][j] = sc.nextInt();
            }
        }
        
        int res = gauss();
        if (res == 0) {
            for (int i = 1; i <= n; i++) {
                System.out.println(g[i][n + 1]);
            }
        } else if (res == 1) {
            System.out.println("Multiple sets of solutions");
        } else {
            System.out.println("No solution");
        }
        
        sc.close();
    }
    
    private static int gauss() {
        
        //枚举每列，找为1的行
        int row = 1;
        for (int col = 1; col <= n; col++) {
            int pos = -1;
            for (int i = row; i <= n; i++) {
                if (g[i][col] == 1) {
                    pos = i;
                    break;
                }
            }
            if (pos == -1) {
                continue;
            }
            //交换
            swap(row, pos);
            //消去下面的1
            for (int i = row + 1; i <= n; i++) {
                if (g[i][col] == 1) {
                    for (int j = 1; j <= n + 1; j++) {
                        g[i][j] ^= g[row][j];
                    }
                }
            }
            
            row++;
        }
        if (row <= n) {
            for (int i = row; i <= n; i++) {
                if (g[i][n + 1] == 1) {
                    //无解
                    return 2;
                }
            }
            //多组解
            return 1;
        }
        
        //消去上面的1
        for (int i = n; i >= 2; i--) {
            for (int j = 1; j <= i - 1; j++) {
                if (g[j][i] == 1) {
                    for (int k = 1; k <= n + 1; k++) {
                        g[j][k] ^= g[i][k];
                    }
                }
            }
        }
        
        return 0;
    }
    
    private static void swap(int a, int b) {
        for (int i = 1; i <= n + 1; i++) {
            int tmp = g[a][i];
            g[a][i] = g[b][i];
            g[b][i] = tmp;
        }
    }
}

8. 求组合数

10w组递推
1w组预处理阶乘（涉及模，所以还要求逆元）
20组，卢卡斯(Lucas)定理

acwing 885. 求组合数 I https://www.acwing.com/problem/content/887/

import java.util.*;

class Main {
    static long[][] c;
    static int N = 2000;
    static long P = (long) 1e9 + 7;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        c = new long[N + 1][N + 1];
        
        c[0][0] = 1;
        
        for (int i = 1; i <= N; i++) {
            c[i][0] = 1;
            for (int j = 1; j <= i; j++) {
                c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % P;
            }
        }
        
        for (int i = 0; i < n; i++) {
            int a = sc.nextInt(), b = sc.nextInt();
            System.out.println(c[a][b]);
        }
        sc.close();
    }
}

acwing 886. 求组合数 II https://www.acwing.com/problem/content/888/

预处理阶乘（涉及模，所以还要求逆元）

import java.util.*;

class Main {
    static long P = (long) 1e9 + 7;
    static long[] jc;
    static long[] ni;
    static int N = (int) 1e5 + 5;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        jc = new long[N];
        ni = new long[N];
        jc[0] = ni[0] = 1;
        for (int i = 1; i < N; i++) {
            jc[i] = (jc[i - 1] * i) % P;
            //ni[i] = fastpow(jc[i], P - 2); 都能ac
            ni[i] = ni[i - 1] * fastpow(i, P - 2) % P;
        }
        
        for (int i = 0; i < n; i++) {
            int a = sc.nextInt(), b = sc.nextInt();
            System.out.println(jc[a] * ni[a - b] % P * ni[b] % P);
        }
        sc.close();
    }
    
    private static long fastpow(long a, long b) {
        long res = 1;
        long t = a;
        while (b != 0) {
            if (b % 2 == 1) {
                res = res * t % P;
            }
            t = t * t % P;
            b >>= 1;
        }
        return res;
    }
    
}

acwing 887. 求组合数 III https://www.acwing.com/problem/content/889/

卢卡斯(Lucas)定理:

如果直接用c(a / P, b / P) * c(a % P, b % P) % P，会无法通过用例10 10 3

因为这个会计算而3这个因子在模3的时候结果为0，而不是1

所以必须保证时（lucas(a / P, b / P) * c(a % P, b % P) % P），才进行计算

import java.util.*;

class Main {
    static long P;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        for (int i = 0; i < n; i++) {
            long a = sc.nextLong(), b = sc.nextLong();
            P = sc.nextInt();
            System.out.println(lucas(a, b));
        }
        sc.close();
    }
    
    private static long lucas(long a, long b) {
        if (a < P && b < P) {
            return c(a, b);
        }
        //a / P不一定保证结果小于P，所以需要递归调用
        return lucas(a / P, b / P) * c(a % P, b % P) % P;
    }
    
    private static long c(long a, long b) {
        long res = 1;
        for (long i = a - b + 1; i <= a; i++) {
            res = res * i % P;
        }
        for (long i = 1; i <= b; i++) {
            res = res * fastpow(i, P - 2) % P;
        }
        return res;
    }
    
    private static long fastpow(long a, long b) {
        long res = 1;
        long t = a;
        while (b != 0) {
            if (b % 2 == 1) {
                res = res * t % P;
            }
            t = t * t % P;
            b >>= 1;
        }
        return res;
    }
    
}

acwing 888. 求组合数 IV https://www.acwing.com/problem/content/description/890/

高精度计算准确值

从定义出发

把上下都用质因数来表示，并相减

最后用高精度乘法，即可求出答案

对于求质因数，用除法求质因数，也能过O(n)

但可以更快，比如求13!中3的个数

13 / 3 = 4，所以1_13中，3的倍数的数共有4个（3，6，9，12）

13 / = 1，所有1_13中，9的倍数的数共有1个（9）

13 < 停止

为什么一定不重不漏？

比如，一定会在除以的时候+1，的时候+1，...，的时候+1

一定且只会加k次

import java.util.*;

class Main {
    static List<Integer> primes;
    static boolean[] flag;
    static int N = 5010;
    static int[] cnt;
    static int size;
    static List<Integer> res;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt(), b = sc.nextInt();
        primes = new ArrayList<>();
        flag = new boolean[N];
        flag[0] = flag[1] = true;
        getPrime();
        
        size = primes.size();
        cnt = new int[size];
        res = new ArrayList<>();
        res.add(1);
        for (int i = 0; i < size; i++) {
            int p = primes.get(i);
            cnt[i] = getCnt(a, p) - getCnt(a - b, p) - getCnt(b, p);
            for (int j = 0; j < cnt[i]; j++) {
                mul(primes.get(i));
            }
        }
        
        
        
        for (int i = res.size() - 1; i >= 0; i--) {
            System.out.print(res.get(i));
        }
        
        sc.close();
    }
    
    private static void mul(int t) {
        int pre = 0;
        for (int i = 0; i < res.size(); i++) {
            int c = res.get(i) * t + pre;
            res.set(i, c % 10);
            pre = c / 10;
        }
        //注意这里pre可能比较大，可能不止进位1次
        while (pre != 0) {
            res.add(pre % 10);
            pre /= 10;
        }
    }
    
    private static void getPrime() {
        for (int i = 2; i < N; i++) {
            if (!flag[i]) {
                primes.add(i);
            }
            for (int j = 0; primes.get(j) * i < N; j++) {
                flag[primes.get(j) * i] = true;
                if (i % primes.get(j) == 0) {
                    break;
                }
            }
        }
    }
    
    private static int getCnt(int x, int p) {
        int res = 0;
        int t = p;
        while (x >= t) {
            res += x / t;
            t *= p;
        }
        return res;
    }
    /*试除法也能过
    private static int getCnt(int x, int p) {
        int res = 0;
        for (int i = 2; i <= x; i++) {
            int t = i;
            while (t % p == 0) {
                t /= p;
                res++;
            }
        }
        return res;
    }
    */
    
}

acwing 889. 满足条件的01序列 https://www.acwing.com/problem/content/891/

由上图可看出，该问题可转化为从（0，0）到（6，6）【向右走的步数大于向上走的步数】的所有路径数

也即路径上的点（x，y）始终满足

正着求不好求，因此用总路径数 - 不满足要求的路径数 = 所求路径数 来计算

总路径数：（0，0）到（6，6）的所有路径数，也即
不满足要求的路径数：也即一定会经过上图中的红线（y = x + 1），从第一次经过红线的点开始，一直到（6，6）这段路径，沿着红线进行对称，因为（6，6）点不会变，其关于红线（y = x + 1）的对称点为（5，7）。所以每一条从（0，0）到（5，7）的路径，一定会经过红线，那么从第一次经过的点开始沿着红线对称，就会变成不满足要求的路径。其数量为

因此，所求路径数 = -

对于含有n个a和n个b的排列（满足任意前缀中，a一定多于或等于b，只有a和b两种情况）来说：

通分，化简后，可化为卡特兰数：

import java.util.*;

class Main {
    static long P = (long) 1e9 + 7;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int N = 2 * n + 10;
        long[] jc = new long[N];
        jc[0] = jc[1] = 1;
        for (int i = 2; i < N; i++) {
            jc[i] = jc[i - 1] * i % P;
        }
        long res = jc[2 * n];
        res = res * fastpow(jc[n], P - 2) % P;
        res = res * fastpow(jc[n], P - 2) % P;
        res = res * fastpow(n + 1, P - 2) % P;
        System.out.println(res);
        sc.close();
    }
    
    public static long fastpow(long x, long a) {
        long res = 1;
        
        long t = x;
        while (a != 0) {
            if (a % 2 == 1) {
                res = res * t % P;
            }
            t = t * t % P;
            a >>= 1;
        }
        
        return res;
    }
}

9. 容斥原理

奇数个+

偶数个-

总共有: 项

（n个物品的所有选法 = 每一个选还是不选）

所以总共有项（除去【全都不选】这项）

acwing 890. 能被整除的数 https://www.acwing.com/problem/content/892/

注意：可能会爆long，所以要么提前中止（大于n时），要么用double

import java.util.*;

class Main {
    static int n, m;
    static int[] primes;
    static long res;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        primes = new int[m];
        
        for (int i = 0; i < m; i++) {
            primes[i] = sc.nextInt();
        }
        
        res = 0;
        dfs(1, 0, 0);
        System.out.println(res);
        
        sc.close();
    }
    
    private static void dfs(long val, int pos, int cnt) {
        if (pos >= m) {
            if (val != 1) {
                if (cnt % 2 == 1) {
                    res += n / val;
                } else {
                    res -= n / val;
                }
            }
            return;
        }
        //不提前中止的话，会爆long
        if (val > n) {
            return;
        }
        dfs(val * primes[pos], pos + 1, cnt + 1);
        dfs(val, pos + 1, cnt);
    }
}

用double，也可AC：

private static void dfs(double val, int pos, int cnt) {
    if (pos >= m) {
        if (val != 1) {
            if (cnt % 2 == 1) {
                res += (long)Math.floor(n / val);
            } else {
                res -= (long)Math.floor(n / val);
            }
        }
        return;
    }

    dfs(val * primes[pos], pos + 1, cnt + 1);
    dfs(val, pos + 1, cnt);
}

用位运算代替dfs：

枚举1 ~ ，每一个数代表一种情况

import java.util.*;

class Main {
    static int n, m;
    static int[] primes;
    static long res;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        primes = new int[m];
        
        for (int i = 0; i < m; i++) {
            primes[i] = sc.nextInt();
        }
        res = 0;
        int N = 1 << m;
        for (int i = 1; i < N; i++) {
            int cnt = 0;
            long val = 1;
            for (int j = 0; j < m; j++) {
                int c = (i >> j) & 1;
                if (c == 1) {
                    cnt++;
                    val *= primes[j];
                    if (val > n) {
                        break;
                    }
                }
            }
            if (val > n) {
                continue;
            }
            if (cnt % 2 == 1) {
                res += n / val;
            } else {
                res -= n / val;
            }
        }
        
        System.out.println(res);
        sc.close();
    }

}

10. 博弈论

acwing 891. Nim游戏 https://www.acwing.com/problem/content/893/

设当前n堆石子的数量分别为，则可以分为以下三种情况：

0 ^ 0 ^ 0 = 0 面临该状态的人输了
^ ^ 0
- ^ ^ = m > 0
- m的二进制表示一定含有1，设其最高位的1是第k位（从0开始）
- 因为是异或，所以中一定至少存在一个的第k位为1（对于第k位，最差就是其他都为0）
- 那么 ^ m = XXXXX1YYYYY ^ 000001ZZZZZ = XXXXX0TTTTT （X、Y、Z、T是任意二进制位，XXXXX比如可取00110）
- ^ m < （因为第k位之后的高位是相等的（都是XXXXX），第k位一个是1，一个是0）
- （ - ^ m） > 0
- 用 - （ - ^ m）替换（相当于拿走（ - ^ m）数量石子，其数量一定大于0，符合要求）
- - （ - ^ m） = ^ m
- ^ ^ ^ ^ = m
- ^ ^ ^ m ^ ^ = m ^ m = 0 （也即拿走（ - ^ m）后，状态转移到，下面第三种情况）
^ ^ = 0
- 只要还能拿石子，该种状态一定会转移到第二种情况
- 证明：（反证法）
- 假设从中拿走k个后，仍然有 ^ ^ ( - k) ^ ^ = 0 （k > 0）
- ^ ^ ^ ^ = 0
- ^ ^ ( - k) ^ ^ = 0
- 两个等式的左边相异或 = 右边相异或
- ^ ( - k) = 0
- 因为k > 0，所以，所以上式不可能成立，故拿走一定数量的石子后，不可能保持第三种状态，也即一定会转移到第二种情况

因此，先手 ^ ^ 0时必胜， ^ ^ = 0时必败

因为 ^ ^ 0时，一定可以拿走（ - ^ m），抛给对手 ^ ^ = 0 （必败的情况）

而 ^ ^ = 0又只能转移到 ^ ^ 0，也就是抛给对手的一定是 ^ ^ 0（必胜的情况）

最后不断地拿走石子，就会变成0 ^ 0 ^ 0 = 0，就输了（始终 ^ ^ = 0状态的选手就一定会输）

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int res = 0;
        for (int i = 0; i < n; i++) {
            res ^= sc.nextInt();
        }
        System.out.println(res != 0 ? "Yes" : "No");
        sc.close();
    }
}

acwing 893. 集合-Nim游戏 https://www.acwing.com/problem/content/895/

Mex运算

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

mex(0,0,0,1,1,2) = 3

mex(2, 5 ,9) = 0

SG函数

在有向图游戏中，对于每个节点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)。

graph LR;
A((x))
A --> B((y1))
A --> C((y2))
A --> D((...))
A --> E((yk))

SG(x) = mex{SG（y1），SG（y2）... SG（yk）}

SG(终点) = 0

举个例子：(这个图表示一个有向图游戏)

graph LR;
A((3)) --> B((2)) --> C((0))
A --> D((1)) --> E((0))
A --> F((1)) --> E
A --> G((0)) --> F
B --> D

不为0就能必胜，因为它可以选择走到0，抛给对手0的局面，让其必败
为0会必败，因为他只能走到非0局面，抛给对手必胜局面

走到终点，为0，就输了（包含在为0的局面中）

如果有多个堆，每一堆都能构造这样的图，此时以起点SG（）代表图1，SG（）代表图2 ...（比如前面用SG（3）代表第一堆石子）

当SG（）^ SG（）^ ...... ^ SG（）= 0 必败

当SG（）^ SG（）^ ...... ^ SG（） 0 必胜

证明：

SG（）^ SG（）^ ...... ^ SG（）= x 0 时

和前面Nim游戏一样，一定能找到【SG（）^ x < SG（）】 SG（） = k > 0

根据SG函数定义，SG一定可以到0，1，2......k-1，也即一定可以将 SG（）替换为SG（）^ x

转移成SG（）^ SG（）^ ...... ^ SG（）= 0 情况

其余的证明和Nim游戏一样

注意：一个节点的分支可能出现重复值（比如 0，0，0，1，2），所以不能通过是否下标=值来判断，而是用set依次判断自然数（0，1，2，3...）是否存在

import java.util.*;

class Main {
    
    static int[] S;
    static int[] dp;
    static int k;
    static int M = 10010;
    
    private static int sg(int x) {
        if (dp[x] != -1) {
            return dp[x];
        }
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < k; i++) {
            if (x >= S[i]) {
                set.add(sg(x - S[i]));
            }
        }
        int t;
        for (t = 0; t < set.size(); t++) {
            if (!set.contains(t)) {
                break;
            }
        }
        dp[x] = t;
        return t;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        k = sc.nextInt();
        S = new int[k];
        dp = new int[M];
        Arrays.fill(dp, -1);
        dp[0] = 0;
        for (int i = 0; i < k; i++) {
            S[i] = sc.nextInt();
        }
        int n = sc.nextInt();
        int res = 0;
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            res ^= sg(x);
        }
        System.out.println(res != 0 ? "Yes" : "No");
        
        sc.close();
    }
}

acwing 892. 台阶-Nim游戏 https://www.acwing.com/problem/content/894/

奇数台阶的所有堆可以看成Nim游戏

对于必败者（奇数台阶上石子异或=0）：

若必败者从偶数台阶拿石子到下一台阶（奇），那么必胜者只需要从下一台阶（奇）拿走相同数量到下下阶（偶）（又抛给了必败者：奇数台阶上石子异或=0）
若必败者从奇数台阶拿石子到下一台阶（偶），那么根据Nim游戏（+k和-k个石子都能用同样方式反证），一定会造成奇数台阶上石子异或！=0，使得对手必胜，必胜者根据Nim游戏拿走 - ^ m个，就再次能使得奇数台阶上石子异或=0，抛给对手必败情况

因为不断向下拿石子，所以最后一定会使得台阶上没有石子（此时奇数台阶上石子异或=0，面临该状态的选手必败）

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int res = 0;
        for (int i = 1; i <= n; i++) {
            int x = sc.nextInt();
            if (i % 2 == 1) {
                res ^= x;
            }
        }
        System.out.println(res != 0 ? "Yes" : "No");
        sc.close();
    }
}

acwing 894. 拆分-Nim游戏 https://www.acwing.com/problem/content/896/

注意题意：其中的放入，指的是放入【新】的两堆石子，取走的那堆就扔了

由于会每个值会严格减小，最后一定都会减小到0

可以将每堆石子，看成一个有向图游戏，其下一个局面就是由一堆石子（x个） ---> 两堆石子（y, z个 > x）

仍然是:

当SG（）^ SG（）^ ...... ^ SG（）= 0 必败

当SG（）^ SG（）^ ...... ^ SG（） 0 必胜

SG（）^ SG（）^ ...... ^ SG（）的下一个局面：

SG（）^ SG（）^ ...... ^ SG（，） ^ ...... ^ SG（）

= SG（）^ SG（）^ ...... ^ （ SG（）^ SG（）） ^ ...... ^ SG（）

因为相当于一个局面拆分成了两个局面，由SG函数理论，多个独立局面的SG值，等于这些局面SG值的异或和。

所以 SG（，）= SG（）^ SG（）（直接记结论）

因此，最后可以看成之前的集合-Nim游戏（ SG（，）相当于之前SG（）拿走一定数量石子后的新局面，当成整体看，以其具体值代替 SG（，），就能沿用之前的证明）

不严谨的解释：

因为SG函数，是能走到比自己小的每一个数

和Nim游戏中的每一堆石子的性质相同

那么， SG（，）就是两堆石子，这样总体局面 SG（，）= SG（）^ SG（）

graph LR;
A((x))
A --> B((SG: y1, z1)) --> G((...))
B --> H((...))
A --> C((SG: y2, z2))
A --> D((...))
A --> E((SG: yk, zk))

import java.util.*;

class Main {
    static int[] dp;
    
    private static int SG(int x) {
        if (dp[x] != -1) {
            return dp[x];
        }
        Set<Integer> set = new HashSet();
        for (int i = 0; i < x; i++) {
            //必须j <= i，为了防止a，b和b，a重复遍历
            for (int j = 0; j <= i; j++) {
                int t = SG(i) ^ SG(j);
                set.add(t);
            }
        }
        int i;
        for (i = 0; i < set.size(); i++) {
            if (!set.contains(i)) {
                break;
            }
        }
        dp[x] = i;
        return i;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        dp = new int[110];
        dp[0] = 0;
        Arrays.fill(dp, -1);
        int res = 0;
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            res ^= SG(x);
        }
        System.out.println(res != 0 ? "Yes" : "No");
        
        sc.close();
    }
}

LOADING