线性代数

相比于数论和组合数学，涉及范围更小。

主要涉及：

• 向量运算（特别是计算几何）；
• 矩阵乘法与矩阵快速幂；
• 高斯消元；
• 线性基；
• 矩阵树定理等 树计数。

可以看这个视频集来增加对线性代数的认识。

向量

物理里又称为矢量。

既有大小又有方向的量成为向量。数学上研究的向量为自由向量，即只要不改变它的大小和方向，起点和终点可以任意平行移动的向量。记作 $\vec a$ 或者 $\mathbf a$。

可以用一个方向+一个大小来描述。

在竞赛中我们一般用一个 $n$ 维点来表示一个 $n$ 维向量。

其含义为从原点到该点的一个向量。

向量与数乘法 点积

可以用来表示多个数与一个相同数的乘积。

在线性代数中，向量分为列向量和行向量。

主要研究对象是列向量（$n\times1$ 维）。

如果想要表示行向量（$1\times n$ 维），需要在向量右上方写转置记号 $T$。行向量在线性代数中一般表示方程。

比如 $a_1x_1+a_2x_2+a_3x_3=b$ 可以表示成：

$$\begin{pmatrix} a_1 & a_2 & a_3 \\ \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix}=b $$

矩阵

$$3 \begin{pmatrix} 2 \\ 3 \\ 4 \end{pmatrix}= \begin{pmatrix} 6 \\ 9 \\ 12 \end{pmatrix} $$$$\begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{pmatrix}± \begin{pmatrix} 6 & 5 & 4 \\ 3 & 2 & 1 \end{pmatrix}= \begin{pmatrix} 7 & 7 & 7 \\ 7 & 7 & 7 \end{pmatrix}/ \begin{pmatrix} -5 & -3 & -1 \\ 1 & 3 & 5 \end{pmatrix} $$$$\begin{pmatrix} 1 & 1 & 1 \end{pmatrix} \begin{pmatrix} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{pmatrix}= \begin{pmatrix} 1 & 2 & 3 \end{pmatrix} $$$$\begin{pmatrix} 1 & 2 & 3 \end{pmatrix} \begin{pmatrix} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{pmatrix}= \begin{pmatrix} 1 & 3 & 6 \end{pmatrix} $$$$\begin{pmatrix} 1 & 3 & 6 \end{pmatrix} \begin{pmatrix} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{pmatrix}= \begin{pmatrix} 1 & 4 & 10 \end{pmatrix} $$

实现

const int mod = /**/,sz = /**/;

struct mat
{
	int a[sz][sz];
	mat()
	{
		memset(a,0,sizeof(a));
	}
	mat operator-(const mat& T) const
	{
		mat res;
		for(int i = 0;i < sz;i++)
		for(int j = 0;j < sz;j++)
		res.a[i][j] = (a[i][j] - T.a[i][j]) % mod;
		return res;
	}
	mat operator+(const mat& T) const
	{
		mat res;
		for(int i = 0;i < sz;i++)
		for(int j = 0;j < sz;j++)
		res.a[i][j] = (a[i][j] + T.a[i][j]) % mod;
		return res;
	}
	mat operator*(const mat& T) const
	{
		mat res;
		int r;
		for(int i = 0;i < sz;i++)
		{
			for(int k = 0;k < sz;k++)
			{
				r = a[i][k];
				for(int j = 0;j < sz;j++)
				{
					res.a[i][j] += T.a[k][j] * r;
					res.a[i][j] %= mod;
				}
			}
		}
		return res;
	}
	mat pw(int x) const
	{
		mat res,bas;
		for(int i = 0;i < sz;i++) res.a[i][i] = 1;
		for(int i = 0;i < sz;i++)
		for(int j = 0;j < sz;j++)
		bas.a[i][j] = a[i][j] % mod;
		while(x)
		{
			if(x & 1) res = res * bas;
			bas = bas * bas;
			x >>= 1;
		}
		return res;
	}
};

题目

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int mod = 1e9 + 7,sz = 101;
int n;

struct mat
{
	int a[sz][sz];
	mat()
	{
		memset(a,0,sizeof(a));
	}
	mat operator-(const mat& T) const
	{
		mat res;
		for(int i = 0;i < sz;i++)
		for(int j = 0;j < sz;j++)
		res.a[i][j] = (a[i][j] - T.a[i][j]) % mod;
		return res;
	}
	mat operator+(const mat& T) const
	{
		mat res;
		for(int i = 0;i < sz;i++)
		for(int j = 0;j < sz;j++)
		res.a[i][j] = (a[i][j] + T.a[i][j]) % mod;
		return res;
	}
	mat operator*(const mat& T) const
	{
		mat res;
		int r;
		for(int i = 0;i < sz;i++)
		{
			for(int k = 0;k < sz;k++)
			{
				r = a[i][k];
				for(int j = 0;j < sz;j++)
				{
					res.a[i][j] += T.a[k][j] * r;
					res.a[i][j] %= mod;
				}
			}
		}
		return res;
	}
	mat pw(int x) const
	{
		mat res,bas;
		for(int i = 0;i < sz;i++) res.a[i][i] = 1;
		for(int i = 0;i < sz;i++)
		for(int j = 0;j < sz;j++)
		bas.a[i][j] = a[i][j] % mod;
		while(x)
		{
			if(x & 1) res = res * bas;
			bas = bas * bas;
			x >>= 1;
		}
		return res;
	}
};

signed main()
{
	scanf("%lld",&n);
	if(n <= 2){printf("1");return 0;}
	mat a,x;
	a.a[0][0] = 1;
	a.a[0][1] = 1;
	a.a[1][0] = 1;
	a = a.pw(n - 2);
	x.a[0][0] = 1;
	x.a[0][1] = 1;
	printf("%lld",(x * a).a[0][0]);
	return 0;
}

题目

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int mod = 1e9 + 7,sz = 101;
int n,k;

struct mat
{
	int a[sz][sz];
	mat()
	{
		memset(a,0,sizeof(a));
	}
	mat operator-(const mat& T) const
	{
		mat res;
		for(int i = 0;i < sz;i++)
		for(int j = 0;j < sz;j++)
		res.a[i][j] = (a[i][j] - T.a[i][j]) % mod;
		return res;
	}
	mat operator+(const mat& T) const
	{
		mat res;
		for(int i = 0;i < sz;i++)
		for(int j = 0;j < sz;j++)
		res.a[i][j] = (a[i][j] + T.a[i][j]) % mod;
		return res;
	}
	mat operator*(const mat& T) const
	{
		mat res;
		int r;
		for(int i = 0;i < sz;i++)
		{
			for(int k = 0;k < sz;k++)
			{
				r = a[i][k];
				for(int j = 0;j < sz;j++)
				{
					res.a[i][j] += T.a[k][j] * r;
					res.a[i][j] %= mod;
				}
			}
		}
		return res;
	}
	mat pw(int x) const
	{
		mat res,bas;
		for(int i = 0;i < sz;i++) res.a[i][i] = 1;
		for(int i = 0;i < sz;i++)
		for(int j = 0;j < sz;j++)
		bas.a[i][j] = a[i][j] % mod;
		while(x)
		{
			if(x & 1) res = res * bas;
			bas = bas * bas;
			x >>= 1;
		}
		return res;
	}
}p,ans;

signed main()
{
	scanf("%lld%lld",&n,&k);
	for(int i = 1;i <= n;i++)
	for(int j = 1;j <= n;j++)
	scanf("%lld",&p.a[i][j]);
	ans = p.pw(k);
	for(int i = 1;i <= n;i++)
	{
		for(int j = 1;j <= n;j++) printf("%lld ",ans.a[i][j]);
		printf("\n");
	}
	return 0;
}

题目

根据题意，$f_n=f_{n-1}+f_{n-2}+\dots+f_{n-k}$，写出矩阵：

$$\begin{bmatrix} f_n\\ f_{n-1}\\ \dots\\ f_{n-k+1} \end{bmatrix} $$

设

$$\begin{bmatrix} f_n\\ f_{n-1}\\ \dots\\ f_{n-k+1} \end{bmatrix}=A\times \begin{bmatrix} f_{n-1}\\ f_{n-2}\\ \dots\\ f_{n-k} \end{bmatrix}=A^2\times \begin{bmatrix} f_{n-2}\\ f_{n-3}\\ \dots\\ f_{n-k-1} \end{bmatrix}=\dots=A^{n-k}\times \begin{bmatrix} f_k\\ f_{k-1}\\ \dots\\ f_1 \end{bmatrix} $$

所以

$$A= \begin{bmatrix} 1 & 1 & \dots & 1\\ 1 & 0 & \dots & 0\\ 0 & 1 & \dots & 0\\ \dots \end{bmatrix} $$

即 $A_{1,i}=A_{i,i-1}=1(i\leq k)$。

因为 $A_{1,1}f_{n-1}+A_{1,2}f_{n-2}+\dots+A_{1,n}f_{n-k}=f_n$，而 $f_1=f_2=\dots=f_k=1$，这样可以凑。

而 $A_{2,1}f_{n-1}+A_{2,2}f_{n-2}+\dots+A_{2,n}f_{n-k}=f_{n-1}$，只把 $A_{2,1}$ 弄成 $1$ 别的都是 $0$ 即可。

以此类推。

$A$ 这样构造。

所以只需弄出 $A^{n-k}$，矩阵快速幂即可。

最终答案是 $\sum\limits_{i=1}^k A_{1,i}$。

因为 $f_1=f_2=\dots=f_k=1$，以矩阵乘法方法和

$$A^{n-k}\times \begin{bmatrix} f_k\\ f_{k-1}\\ \dots\\ f_1 \end{bmatrix} $$

这个式子就行。

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int mod = 1e9 + 7,sz = 101;
int n,k,sum;

struct mat
{
	int a[sz][sz];
	mat()
	{
		memset(a,0,sizeof(a));
	}
	mat operator-(const mat& T) const
	{
		mat res;
		for(int i = 0;i < sz;i++)
		for(int j = 0;j < sz;j++)
		res.a[i][j] = (a[i][j] - T.a[i][j]) % mod;
		return res;
	}
	mat operator+(const mat& T) const
	{
		mat res;
		for(int i = 0;i < sz;i++)
		for(int j = 0;j < sz;j++)
		res.a[i][j] = (a[i][j] + T.a[i][j]) % mod;
		return res;
	}
	mat operator*(const mat& T) const
	{
		mat res;
		int r;
		for(int i = 0;i < sz;i++)
		{
			for(int k = 0;k < sz;k++)
			{
				r = a[i][k];
				for(int j = 0;j < sz;j++)
				{
					res.a[i][j] += T.a[k][j] * r;
					res.a[i][j] %= mod;
				}
			}
		}
		return res;
	}
	mat pw(int x) const
	{
		mat res,bas;
		for(int i = 0;i < sz;i++) res.a[i][i] = 1;
		for(int i = 0;i < sz;i++)
		for(int j = 0;j < sz;j++)
		bas.a[i][j] = a[i][j] % mod;
		while(x)
		{
			if(x & 1) res = res * bas;
			bas = bas * bas;
			x >>= 1;
		}
		return res;
	}
}a;

signed main()
{
	scanf("%lld%lld",&n,&k);
	for(int i = 0;i < k;i++)
	{
		a.a[0][i] = 1;
		if(i > 0) a.a[i][i - 1] = 1;
	}
	a = a.pw(n - k);
	for(int i = 0;i < k;i++) sum += a.a[0][i],sum %= mod;
	printf("%lld",sum);
	return 0;
}

题目

我的矩阵是：

$$A= \begin{bmatrix} 1 & 1 & 0 & 1 & 0 & \dots\\ 1 & 0 & 0 & 0 & 0 & \dots\\ 0 & 1 & 0 & 0 & 0 & \dots\\ 0 & 0 & 1 & 0 & 0 & \dots\\ \dots \end{bmatrix} $$

因为

$$\begin{bmatrix} n\\ n-1\\ \dots\\ 1\\ \end{bmatrix}=A\times \begin{bmatrix} n-1\\ n-2\\ \dots\\ 1\\ \end{bmatrix}=A^2\times \begin{bmatrix} n-2\\ n-3\\ \dots\\ 1\\ \end{bmatrix}=A^k\times \begin{bmatrix} a4\\ a3\\ a2\\ a1\\ \end{bmatrix} $$

由 $A$ 的幂是 $1$ 时第一个是 $n-1$ 得 $n-k=4$，所以 $k=n-4$。

根据 $f_i=f_{i−1}+f_{i−2}+f_{i−4}$ 得出 $A$。

然后得出 $A^{n-4}$。

然后乘：

$$\begin{bmatrix} a4\\ a3\\ a2\\ a1\\ \end{bmatrix}$$

即可。

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int mod = 10007,sz = 101;
int n,a1,a2,a3,a4;

struct mat
{
	int a[sz][sz];
	mat()
	{
		memset(a,0,sizeof(a));
	}
	mat operator-(const mat& T) const
	{
		mat res;
		for(int i = 0;i < sz;i++)
		for(int j = 0;j < sz;j++)
		res.a[i][j] = (a[i][j] - T.a[i][j]) % mod;
		return res;
	}
	mat operator+(const mat& T) const
	{
		mat res;
		for(int i = 0;i < sz;i++)
		for(int j = 0;j < sz;j++)
		res.a[i][j] = (a[i][j] + T.a[i][j]) % mod;
		return res;
	}
	mat operator*(const mat& T) const
	{
		mat res;
		int r;
		for(int i = 0;i < sz;i++)
		{
			for(int k = 0;k < sz;k++)
			{
				r = a[i][k];
				for(int j = 0;j < sz;j++)
				{
					res.a[i][j] += T.a[k][j] * r;
					res.a[i][j] %= mod;
				}
			}
		}
		return res;
	}
	mat pw(int x) const
	{
		mat res,bas;
		for(int i = 0;i < sz;i++) res.a[i][i] = 1;
		for(int i = 0;i < sz;i++)
		for(int j = 0;j < sz;j++)
		bas.a[i][j] = a[i][j] % mod;
		while(x)
		{
			if(x & 1) res = res * bas;
			bas = bas * bas;
			x >>= 1;
		}
		return res;
	}
}a,x;

signed main()
{
	scanf("%lld%lld%lld%lld%lld",&n,&a1,&a2,&a3,&a4);
	for(int i = 1;i < 4;i++) a.a[i][i - 1] = 1;
	a.a[0][0] = 1;
	a.a[0][1] = 1;
	a.a[0][3] = 1;
	a = a.pw(n - 4);
	x.a[0][0] = a4;
	x.a[1][0] = a3;
	x.a[2][0] = a2;
	x.a[3][0] = a1;
	a = a * x;
	printf("%lld",a.a[0][0]);
	return 0;
}

题目

先写出正常 $dp$ 代码：

#include <bits/stdc++.h>
using namespace std;

const int mod = 10000;

int n,f[1000001],g[1000001];

signed main()
{
	scanf("%d",&n);
	f[0] = 1;
	f[1] = g[1] = 1;
	for(int i = 2;i <= n;i++)
	{
		f[i] = ((f[i - 1] + f[i - 2]) % mod + 2 * g[i - 2] % mod) % mod;
		g[i] = (g[i - 1] + f[i - 1]) % mod;
	}
	printf("%d",f[n]);
	return 0;
}

$f_i$ 为截止到 $i$ 时的答案，$g_i$ 是楼梯方块。具体看洛谷。

写出矩阵：

$$\begin{bmatrix} f_n\\ f_{n-1}\\ g_{n-1} \end{bmatrix}=A\times \begin{bmatrix} f_{n-1}\\ f_{n-2}\\ g_{n-2} \end{bmatrix}=A^k\times \begin{bmatrix} f_1\\ f_0\\ g_0 \end{bmatrix} $$

因为 $n-k=1$，所以 $k=n-1$。

$$A= \begin{bmatrix} 1 & 1 & 2\\ 1 & 0 & 0\\ 0 & 1 & 1 \end{bmatrix} $$

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int mod = 10000,sz = 101;
int n;

struct mat
{
	int a[sz][sz];
	mat()
	{
		memset(a,0,sizeof(a));
	}
	mat operator-(const mat& T) const
	{
		mat res;
		for(int i = 0;i < sz;i++)
		for(int j = 0;j < sz;j++)
		res.a[i][j] = (a[i][j] - T.a[i][j]) % mod;
		return res;
	}
	mat operator+(const mat& T) const
	{
		mat res;
		for(int i = 0;i < sz;i++)
		for(int j = 0;j < sz;j++)
		res.a[i][j] = (a[i][j] + T.a[i][j]) % mod;
		return res;
	}
	mat operator*(const mat& T) const
	{
		mat res;
		int r;
		for(int i = 0;i < sz;i++)
		{
			for(int k = 0;k < sz;k++)
			{
				r = a[i][k];
				for(int j = 0;j < sz;j++)
				{
					res.a[i][j] += T.a[k][j] * r;
					res.a[i][j] %= mod;
				}
			}
		}
		return res;
	}
	mat pw(int x) const
	{
		mat res,bas;
		for(int i = 0;i < sz;i++) res.a[i][i] = 1;
		for(int i = 0;i < sz;i++)
		for(int j = 0;j < sz;j++)
		bas.a[i][j] = a[i][j] % mod;
		while(x)
		{
			if(x & 1) res = res * bas;
			bas = bas * bas;
			x >>= 1;
		}
		return res;
	}
}a,x;

signed main()
{
	scanf("%lld",&n);
	a.a[0][0] = a.a[0][1] = a.a[1][0] = a.a[2][1] = a.a[2][2] = 1;
	a.a[0][2] = 2;
	a = a.pw(n - 1);
	x.a[0][0] = 1;
	x.a[1][0] = 1;
	a = a * x;
	printf("%lld",a.a[0][0]);
	return 0;
}