Hanwan Space

线性代数的一些板子


这篇 Blog 记录了一些线性代数的板子,以便不时之需。

矩阵快速幂

cpp
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int maxN = 105;
struct matrix{
	long long a[maxN][maxN];
}mat, m1;
long long n, p;
matrix operator*(matrix x, matrix y) {
	matrix z;
	for (long long i = 1; i <= n; i++)
		for (long long j = 1; j <= n; j++) {
			z.a[i][j] = 0;
			for (long long k = 1; k <= n; k++)
				z.a[i][j] = (z.a[i][j] + x.a[i][k] * y.a[k][j]) % MOD;
		}
	return z;
}
matrix ident(long long k) {
	matrix id;
	for (long long i = 1; i <= k; i++)
		for (long long j = 1; j <= k; j++)
			if (i == j) id.a[i][j] = 1;
			else id.a[i][j] = 0;
	return id;
}
matrix qpow(matrix s, long long k) {
	matrix res = ident(n);
	for ( ; k; k >>= 1, s = s * s)
		if (k & 1) res = res * s;
	return res;
}
int main() {
	cin >> n >> p;
	for (long long i = 1; i <= n; i++)
		for (long long j = 1; j <= n; j++)
			cin >> mat.a[i][j];
	matrix ans = qpow(mat, p);
	for (long long i = 1; i <= n; i++) {
		for (long long j = 1; j <= n; j++)
			cout << ans.a[i][j] << ' ';
		cout << endl;
	}
	return 0;
}

矩阵加速的斐波那契

(1110)\begin{pmatrix}1 & 1 \\ 1 & 0\end{pmatrix}

cpp
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int maxN = 5;
const int N = 2;
struct matrix{
	long long a[maxN][maxN];
}mat;
long long p;
matrix operator*(matrix x, matrix y) {
	matrix z;
	for (long long i = 1; i <= N; i++)
		for (long long j = 1; j <= N; j++) {
			z.a[i][j] = 0;
			for (long long k = 1; k <= N; k++)
				z.a[i][j] = (z.a[i][j] + x.a[i][k] * y.a[k][j]) % MOD;
		}
	return z;
}
matrix ident() {
	matrix id;
	id.a[1][1] = id.a[2][2] = 1;
	id.a[2][1] = id.a[1][2] = 0;
	return id;
}
matrix qpow(matrix s, long long k) {
	matrix res = ident();
	for ( ; k; k >>= 1, s = s * s)
		if (k & 1) res = res * s;
	return res;
}
int main() {
	cin >> p;
	mat.a[1][1] = mat.a[1][2] = mat.a[2][1] = 1;
	mat.a[2][2] = 0;
	matrix ans = qpow(mat, p);
	cout << ans.a[2][1] << endl;
	return 0;
}

  • 代数
  • 板子
© hawa130转载请注明出处
License: CC BY-NC-SA 4.0

上一篇

Hello,World!

下一篇

数论的一些板子