矩阵乘法+快速幂

此题并非dp问题，是为了后面的蓝桥杯真题铺垫知识点。

矩阵乘法：

矩阵 $A$ 显然是存在的。

那么我们如果想求$F_n$

则有：$$F_n=F_{n-1}\cdot A$$

所以：$$F_n=F_1\cdot A^{n-1}$$

矩阵乘法是有结合律的，所以可以用快速幂来求。

接下来构造我们本题的矩阵，$S_n$ 是本题要求的前 $n$ 项和：

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    static final int N = 3;
    static int n, m;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt(); m = sc.nextInt();
        long[] f1 = {1, 1, 1}; // f1 fn+1 S1
        long[][] a = { // A
                {0, 1, 0},
                {1, 1, 1},
                {0, 0, 1}
        };

        n--; // A^n-1
        while (n > 0) { // 快速幂模板
            if ((n & 1) == 1) mul(f1, f1, a); // res = res * a
            mul(a, a, a); // a = a * a
            n >>= 1;
        }

        System.out.println(f1[2]); // Sn
    }

    // 矩阵乘法
    private static void mul(long[] c, long[] a, long[][] b) {
        long[] temp = new long[N];
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                temp[i] = (temp[i] + a[j] * b[j][i]) % m;

        System.arraycopy(temp, 0, c, 0, N); // 拷贝数组
    }

    private static void mul(long[][] c, long[][] a, long[][] b) {
        long[][] temp = new long[N][N];
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                for (int k = 0; k < N; k++)
                    temp[i][j] = (temp[i][j] + a[i][k] * b[k][j]) % m;

        System.arraycopy(temp, 0, c, 0, N); // 拷贝数组
    }
}

JavaB组第8题

完全背包问题+数论

假设我们有 $N$ 个蒸笼，每个蒸笼的包子分别为 $A_1,A_2...A_n$，且他们的最大公约数是 $d$，且 $d>1$，所有数都是 $d$ 的倍数，如果一个数不能被 $d$ 整数，则说明这个数也一定不能被 $A_1,A_2...A_n$ 凑出来，所以此时会有正无穷 $INF$ 个数凑不出来。

当 $gcd(A_1,A_2...A_n)=1$ 时，不能凑出来的数一定是有限个，这是依据裴蜀定理，裴蜀定理是基于两个数 $a,b$ 的定理，当 $gcd(a,b)=1$ 时，最大不能表示的数是：$(a-1)(b-1)-1$， 当有 $N$ 个数时定理也同样适用，当数变多时，这个上界必然会更小，因为可选的数变多了，因为 $1\le N\le 100$，小于 $100$ 中最大互质的两个数是 $98,99$，所以这里的上界我们取到 $10000$ 即可。

此时这个问题就变成了完全背包问题，在 $10000$ 以内有多少个数不能被组合出来。

闫式DP分析法

此时的状态转移方程：$f(i,j)=f(i-1,j)|f(i-1,j-A_i)|f(i-1,j-2A_i)|...|f(i-1,j\le 0)$

时间复杂度为 $O(N^3)$，状态的数量是 $N^2$ 个，转移的数量是 $N$ 个，显然是需要 优化一下的，一般的背包问题时间复杂度是 $O(N^2)$。

我们做一下 $j$ 的变量变换：$f(i,j-A_i)=f(i-1,j-A_i)|f(i-1,j-2A_i)|f(i-1,j-3A_i)|...$

此时这个等式可以替换为第一个等式从第二项开始后面的所有项：

状态转移方程优化为：$f(i,j)=f(i-1,j)|f(i,j-A_i)$

import java.util.Scanner;

public class Main {
    
    static final int N = 110, M = 10010;
    static int[] a = new int[N];
    static boolean[][] f = new boolean[N][M];
    
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	int n = sc.nextInt();
    	int d = 0;
    	for (int i = 1; i <= n; i++) {
    	    a[i] = sc.nextInt();
    	    d = gcd(d, a[i]);
    	}

        if (d != 1) System.out.println("INF"); // 最大公约数不为1 有无限多个数凑不出来
        else {
            f[0][0] = true; // 0件物品 体积为0时也是一种方案
            for (int i = 1; i <= n; i++) {
                for (int j = 0; j < M; j++) {
                    f[i][j] = f[i - 1][j]; // 第一项一定存在
                    if (j >= a[i]) f[i][j] |= f[i][j - a[i]]; // 第二项不一定存在 用或"|"
                }
            }
            
            int res = 0;
            for (int i = 0; i < M; i++) {
                if (!f[n][i]) res++;
            }

    	    System.out.println(res);
        }
    }
    
    private static int gcd(int a, int b) {
        return b != 0 ? gcd(b, a % b) : a;
    }
}

我们发现我们的方程第 $i$ 维只依赖于第 $i$ 和 $i-1$ 项，所以我们可以将数组优化成一维：

import java.util.Scanner;

public class Main {
    
    static final int N = 110, M = 10010;
    static int[] a = new int[N];
    static boolean[] f = new boolean[M];
    
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	int n = sc.nextInt();
    	int d = 0;
    	for (int i = 1; i <= n; i++) {
    	    a[i] = sc.nextInt();
    	    d = gcd(d, a[i]);
    	}

        if (d != 1) System.out.println("INF"); // 最大公约数不为1 有无限多个数凑不出来
        else {
            f[0] = true; // 0件物品 体积为0时也是一种方案
            for (int i = 1; i <= n; i++) {
                for (int j = a[i]; j < M; j++) {
                    f[j] |= f[j - a[i]];
                }
            }
            
            int res = 0;
            for (int i = 0; i < M; i++) {
                if (!f[i]) res++;
            }

    	    System.out.println(res);
        }
    }
    
    private static int gcd(int a, int b) {
        return b != 0 ? gcd(b, a % b) : a;
    }
}

JavaB组第9题

DP+矩阵乘法+快速幂

我们要把 $n$ 个骰子一个一个往上摞，骰子一共有6个面，本题是有 $m$ 组互斥的数，假如互斥数是 $1,2$，那么骰子在垒时，上下两个紧贴的面就不能是 $1$ 和 $2$，求有多少种不同垒骰子的方案数。

闫式DP分析法

当然这是没有去掉不合理的方案总数。

这题太难理解了，没有继续了。