乘法快速幂：
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阶：
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.最终得到的矩阵中答案的位置
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维矩阵
// 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维的方法求出答案矩阵
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天连续迟到的种类数，把各种情况压缩为二维，分别求出各种情况的递推关系。最后累加即可
