快速幂、矩阵快速幂

乘法快速幂：

P1226 【模板】快速幂 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;public class Code01_QuickPower {public static long a, b, p;public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));StreamTokenizer in = new StreamTokenizer(br);PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));in.nextToken();a = (int) in.nval;in.nextToken();b = (int) in.nval;in.nextToken();p = (int) in.nval;out.println(a + "^" + b + " mod " + p + "=" + power());out.flush();out.close();br.close();}public static int power() {long ans = 1;while (b > 0) {if ((b & 1) == 1) {ans = (ans * a) % p;}a = (a * a) % p;b >>= 1;}return (int) ans;}}

对于a^b，把b看作二进制形式，让a从1次方开始，只要b的二进制形式某位上有1，就把此时的a加入(a不断的自乘的幂就对应二进制的每一位)。时间复杂度为logb

矩阵的乘法：

vector<vector<int>> f(vector<vector<int>>& a, vector<vector<int>>& b) {int n = a.size();int m = b[0].size();int k = a[0].size();vector<vector<int>>ans(n, vector<int>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {for (int h = 0; h < k; h++) {ans[i][j] += a[i][h] * b[h][j];}}}return ans;
}

矩阵快速幂：前提矩阵必须是方阵。大体流程和乘法的快速幂是一样的

vector<vector<int>> power(vector<vector<int>>& a, int p) {int n = a.size();vector<vector<int>>ans(n,vector<int>(n,0));for (int i = 0; i < n; i++) {//设为单位阵ans[i][i] = 1;}while (p > 0) {if (p & 1)ans=f(ans, a);a = f(a, a);p>>=1;}return ans;
}

利用矩阵快速幂解决的问题：优化dp问题

1.固定关系的1维k阶表达式(即某一项只有一个维度，是由前好几项推出的，且递推关系式是固定的)，时间复杂度为O(logn*k^3)。关系矩阵的第1列由递推关系确定，剩下的项待定系数求出

2.固定关系的k维1阶表达式(即某一项中有好几个维度，但只需要前一项就可以求出)

1维k阶：

509. 斐波那契数 - 力扣（LeetCode）

class Solution {
public:vector<vector<int>> f(vector<vector<int>>& a, vector<vector<int>>& b) {//矩阵乘法int n = a.size();int m = b[0].size();int k = a[0].size();vector<vector<int>> ans(n, vector<int>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {for (int h = 0; h < k; h++) {ans[i][j] += a[i][h] * b[h][j];}}}return ans;}vector<vector<int>> power(vector<vector<int>>& a, int p) {//矩阵快速幂int n = a.size();vector<vector<int>> ans(n, vector<int>(n, 0));for (int i = 0; i < n; i++) { // 设为单位阵ans[i][i] = 1;}while (p > 0) {if (p & 1)ans = f(ans, a);a = f(a, a);p >>= 1;}return ans;}int fib(int n) {if (n == 0)return 0;if (n == 1)return 1;vector<vector<int>> start = {{1, 0}};//初始数据逆序排列vector<vector<int>> base = {{1, 1}, {1, 0}};//关系矩阵vector<vector<int>> rem = power(base, n - 1);vector<vector<int>> ans = f(start, rem);return ans[0][0];}
};

注意：1.初始数据构成的矩阵的排列方式 2.关系矩阵的构成 3.最终得到的矩阵中答案的位置

70. 爬楼梯 - 力扣（LeetCode）

class Solution {
public:vector<vector<long>> f(vector<vector<long>> a, vector<vector<long>> b) {int n = a.size();int m = b[0].size();int k = a[0].size();vector<vector<long>> ans(n, vector<long>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {for (int h = 0; h < k; h++) {ans[i][j] += a[i][h] * b[h][j];}}}return ans;}vector<vector<long>> power(vector<vector<long>> a, int p) {int n = a.size();vector<vector<long>> ans(n, vector<long>(n, 0));for (int i = 0; i < n; i++) { // 设为单位阵ans[i][i] = 1;}while (p > 0) {if (p & 1)ans = f(ans, a);a = f(a, a);p >>= 1;}return ans;}int climbStairs(int n) {if (n==0||n == 1)return 1;vector<vector<long>> start = {{1, 1}};vector<vector<long>> base = {{1, 1}, {1, 0}};vector<vector<long>> rem = power(base, n - 1);vector<vector<long>> ans = f(start, rem);return ans[0][0];}
};

和斐波那契数列一样，只是0项为1

1137. 第 N 个泰波那契数 - 力扣（LeetCode）

class Solution {
public:vector<vector<long>> f(vector<vector<long>> a, vector<vector<long>> b) {int n = a.size();int m = b[0].size();int k = a[0].size();vector<vector<long>> ans(n, vector<long>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {for (int h = 0; h < k; h++) {ans[i][j] += a[i][h] * b[h][j];}}}return ans;}vector<vector<long>> power(vector<vector<long>> a, int p) {int n = a.size();vector<vector<long>> ans(n, vector<long>(n, 0));for (int i = 0; i < n; i++) { // 设为单位阵ans[i][i] = 1;}while (p > 0) {if (p & 1)ans = f(ans, a);a = f(a, a);p >>= 1;}return ans;}int tribonacci(int n) {if (n == 0)return 0;if (n == 1 || n == 2)return 1;vector<vector<long>> start = {{1, 1, 0}};vector<vector<long>> base = {{1, 1, 0}, {1, 0, 1}, {1, 0, 0}};vector<vector<long>> rem = power(base, n - 2);vector<vector<long>> ans = f(start, rem);return ans[0][0];}
};

此时的递推关系为3维，所以关系矩阵为3维矩阵

790. 多米诺和托米诺平铺 - 力扣（LeetCode）

// f(1) = 1// f(2) = 2// f(3) = 5// f(4) = 11// f(n) = 2 * f(n-1) + f(n-3)// 打表或者公式化简都可以发现规律，这里推荐打表找规律public static void main(String[] args) {for (int i = 1; i <= 9; i++) {System.out.println("铺满 2 * " + i + " 的区域方法数 : " + f(i, 0));}}// 暴力方法// 为了找规律// 如果h==0，返回2*n的区域铺满的方法数// 如果h==1，返回1 + 2*n的区域铺满的方法数public static int f(int n, int h) {if (n == 0) {return h == 0 ? 1 : 0;}if (n == 1) {return 1;}if (h == 1) {return f(n - 1, 0) + f(n - 1, 1);} else {return f(n - 1, 0) + f(n - 2, 0) + 2 * f(n - 2, 1);}}

此题先通过打表找规律，观察推出递推关系式

class Solution {
public:static const int mod=1000000007;vector<vector<long>> f(vector<vector<long>>& a, vector<vector<long>>& b) {int n = a.size();int m = b[0].size();int k = a[0].size();vector<vector<long>> ans(n, vector<long>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {for (int h = 0; h < k; h++) {ans[i][j] = (ans[i][j]+a[i][h] * b[h][j])%mod;}}}return ans;}vector<vector<long>> power(vector<vector<long>>& a, int p) {int n = a.size();vector<vector<long>> ans(n, vector<long>(n, 0));for (int i = 0; i < n; i++) { // 设为单位阵ans[i][i] = 1;}while (p > 0) {if (p & 1)ans = f(ans, a);a = f(a, a);p >>= 1;}return ans;}int numTilings(int m) {int n=m-1;if(n==0)return 1;if(n==1)return 2;if(n==2) return 5;vector<vector<long>>start={{5,2,1}};vector<vector<long>>base={{2,1,0},{0,0,1},{1,0,0}};vector<vector<long>>rem=power(base,n-2);vector<vector<long>>ans=f(start,rem);return (int)ans[0][0];}
};

注：对于方阵幂的次数，从0项开始，求第n项，且递推表达式维度为k维，则幂的次数为(n-(k-1))

k维1阶：

1220. 统计元音字母序列的数目 - 力扣（LeetCode）

class Solution {
public:static const int mod = 1000000007;vector<vector<long>> f(vector<vector<long>> a, vector<vector<long>> b) {int n = a.size();int m = b[0].size();int k = a[0].size();vector<vector<long>> ans(n, vector<long>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {for (int h = 0; h < k; h++) {ans[i][j] = (ans[i][j] + a[i][h] * b[h][j]) % mod;}}}return ans;}vector<vector<long>> power(vector<vector<long>> a, int p) {int n = a.size();vector<vector<long>> ans(n, vector<long>(n, 0));for (int i = 0; i < n; i++) { // 设为单位阵ans[i][i] = 1;}while (p > 0) {if (p & 1)ans = f(ans, a);a = f(a, a);p >>= 1;}return ans;}int countVowelPermutation(int n) {vector<vector<long>> start = {{1, 1, 1, 1, 1}};vector<vector<long>> base = {{0, 1, 0, 0, 0},{1, 0, 1, 0, 0},{1, 1, 0, 1, 1},{0, 0, 1, 0, 1},{1, 0, 0, 0, 0}};int sum = 0;vector<vector<long>> rem = power(base, n - 1);vector<vector<long>> ans = f(start, rem);for (auto i : ans[0])sum = (sum + i) % mod;return sum;}
};

dp[i][k]表示长度为i中以k字符结尾的合法字符串有多少种，最后将5种不同的字符累加求和即可。通过递推关系可知，每项至于前一项有关，且每一项的维度有多个，所以此时可以根据递推关系写出关系表达式，然后按照k阶1维的方法求出答案矩阵

552. 学生出勤记录 II - 力扣（LeetCode）

class Solution {
public:static const int mod = 1000000007;vector<vector<long>> f(vector<vector<long>> a, vector<vector<long>> b) {int n = a.size();int m = b[0].size();int k = a[0].size();vector<vector<long>> ans(n, vector<long>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {for (int h = 0; h < k; h++) {ans[i][j] = (ans[i][j] + a[i][h] * b[h][j]) % mod;}}}return ans;}vector<vector<long>> power(vector<vector<long>> a, int p) {int n = a.size();vector<vector<long>> ans(n, vector<long>(n, 0));for (int i = 0; i < n; i++) { // 设为单位阵ans[i][i] = 1;}while (p > 0) {if (p & 1)ans = f(ans, a);a = f(a, a);p >>= 1;}return ans;}int checkRecord(int n) {vector<vector<long>> start = {{1, 1, 0, 1, 0, 0}};vector<vector<long>> base = {{1, 1, 0, 1, 0, 0}, {1, 0, 1, 1, 0, 0},{1, 0, 0, 1, 0, 0}, {0, 0, 0, 1, 1, 0},{0, 0, 0, 1, 0, 1}, {0, 0, 0, 1, 0, 0}};vector<vector<long>> rem = power(base, n - 1);int sum = 0;vector<vector<long>> ans = f(start, rem);for (auto i : ans[0])sum = (sum + i) % mod;return sum;}
};

定义dp[i][j][k]表示长度为i且缺勤次数为j且最后有k天连续迟到的种类数，把各种情况压缩为二维，分别求出各种情况的递推关系。最后累加即可