前置知识:矩阵乘法,快速幂
很喜欢我们科学老师的一句话:
有时候证明可以写一黑板,但可以想。
这篇文章某些深奥的内容可能要感性理解。
有些时候,我们经常遇到类似函数的求值:
这些类型的递推被称为线性递推。一个朴素的算法是直接递推。但世界上有个好东西,叫矩阵。
入门
我们以斐波那契数列为例。 构造 ,即 和 。
再是 ,设 ,可以发现 。
来观察一下发生的过程。
设 ,,则 。
因此,。
那怎么计算 呢?使用快速幂计算 即可。
现在,省选与你(可能)有缘。
构造矩阵的技巧
假设我们用一行存储系数矩阵(),则若第 项的求和方法中包含 ,则 ,在相乘时 与 相乘累加到答案的第 项上,这个过程需要对矩阵乘法有较直观的理解,建议深入思考一下。
# 10375 矩阵加速入门 6
非常经典。如果只有 (入门 3),应用技巧,, 要保存上一次的 ,即 ,所以 。再是 ,所以 ,。
现在处理那三个系数。
好写,开一个矩阵项纪录 ,每次加上 (所以还有一个矩阵项是常数 )。将 分解得 ,接下来好处理。
给出两个矩阵。
int a[1][5] = {1, 1, 1, 3, 9};// f(n-1) f(n) 1 n n^2
int b[5][5] =
{{0, b, 0, 0, 0},
{1, a, 0, 0, 0},
{0, 1, 1, 1, 1},
{0, 1, 0, 1, 2},
{0, 1, 0, 0, 1}
};
矩阵的模板下面代码里有。
练习
LG P1962 斐波那契数列
思路见上。
#include<bits/stdc++.h>
#define int long long
int mod = 1000000007 ;
using namespace std;
struct Matrix{
private:
int r,c;
vector<vector<int> >mat;
public:
void init(int x, int y, void *p) {
r = x, c = y;
mat.clear();
int (*q)[y] = (int (*)[y])(p);
for(int i = 0;i < x;i ++) {
vector<int>vec;
for(int j = 0;j < y;j ++)
vec.push_back(q[i][j]);
mat.push_back(vec);
}
}
void init(int x, int y) {
r = x, c = y;
mat.clear();
for(int i = 0;i < x;i ++) {
vector<int>vec;
for(int j = 0;j < y;j ++)
vec.push_back(0);
mat.push_back(vec);
}
}
Matrix operator*(Matrix &b) {
Matrix ans;
ans.init(r, b.c);
if(c != b.r) {
cout << "MulError: C != R" << endl;
exit(0);
}
for(int i = 0;i < r;i ++)
for(int j = 0;j < b.c;j ++) {
int sum = 0;
for(int k = 0;k < c;k ++)
sum += mat[i][k] * b.mat[k][j], sum %= mod;
ans.mat[i][j] = sum;
}
return ans;
}
void put(int x, int y) {
cout << mat[x][y];
}
};
int x[1][2] = {1, 1};
int b[2][2] =
{{0, 1},
{1, 1},
};
Matrix qpow(int a) {
Matrix ans, base;
ans.init(1, 2, x);
base.init(2, 2, b);
while(a) {
if(a % 2)
ans = ans * base;
base = base * base;
a >>= 1;
}
return ans;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n;
cin >> n;
if(n == 0)
cout << 1;
if(n <= 2)
cout << x[0][n - 1];
else
qpow(n - 2).put(0, 1);
cout << endl;
return 0;
}
LG P4838 P哥破解密码
可惜啊,以前是紫的。
设 表示答案,推一下发现 。算一下 ,然后就是模板级别的应用。
LG P4910 帕秋莉的手环
每次,我们可以在手环的末尾放入一个金属性、木属性的珠子。可以发现,如果末尾是木属性,下一个珠子就不会是木属性,因此我们把金属性和木属性绑定,每次只能添加一个金属性或“金属性+木属性”,可以证明不影响答案。现在就变成了斐波那契数列,只不过 (金木,金金,木金)。
AT ABC293E Geometric Progression
等比数列求和。一眼定真, 可能不为质数,,因为每次增加一个 ,相当于原等比数列每一项乘 ,再在头部加上 。
共 3 条回复
最后一个。。。
不错 👍
@cookiebus 投稿青藤周报