线性代数相关OJ题选讲

这篇文章是关于线性代数的OJ题选讲,这几道题目都不难,主要是考察思维的灵活程度。


Fast Matrix Calculation

2014 Multi-University Training Contest 9, available at HDUOJ 4965

给定 $N\times k$ 的矩阵 $A$,$k \times N$ 的矩阵 $B$ $(2 \leq k \leq 6, 4 \leq N \leq 1000)$:
Step 1. 计算 $N \times N$ 的矩阵 $C = AB$.
Step 2. 计算 $M = C^{N \times N} \bmod 6$.
Step 3. 输出 $M$ 中所有元素的和.

题解

根据矩阵乘法的结合律,

\[M = (AB)^{N \times N} = A (BA)^{N \times N – 1} B\]

时间复杂度由裸的快速幂$O(N^3 \log N)$变成了$O(N^2k + Nk^2 + k^3 \log N)$。


Matrix Multiplication

2014 Multi-University Training Contest 5, available at HDUOJ 4920

给定$n \times n$的矩阵$A, B$,求模3意义下的乘积。 $(1 \leq n \leq 800)$

题解

令 $M_x$: $M_x(i, j) = [M(i, j) = x]$.

\[ AB = (A_1 – A_2)(B_1 – B_2) = A_1B_1 – A_1B_2 – A_2B_1 + A_2B_2 \]

其中 $A_1, A_2, B_1, B_2$ 是 01矩阵. 使用 std::bitset,可以做做到$O(4n^3/wordsize)$。

(当然,使用其他一些优秀的卡常方法也能过这题)


Matrix Revolution

HDUOJ 1759

给定一个 $n \times n$ 的矩阵 $A$,计算下述矩阵的非零元素的数量

\[ A + A^2 + \cdots + A^k\]

$A$ 是稀疏矩阵,用 $m$ 个三元组 $(a, b, c)$ 表示,每个三元组代表 $A_{ab} = c$。此外,保证主对角线上的元素全为 1。其他元素均为0。

$(0 \leq n \leq 1000, 0 \leq m \leq 10n, n < k < 10^{100}, 0 < c < 10^9)$

题解

利用图的邻接矩阵表示,可知答案就是距离不超过 $k$ 的点对数。


Matrix Multiplication

POJ 3318

给定 $n \times n$ 的矩阵 $A, B, C$。判断$A B = C$是否成立。$(n \leq 500, |A_{ij}|, |B_{ij}| \leq 100, |C_{ij}| \leq 10,000,000)$

提示:有多组测试数据,$O(n^3)$ 的算法会 TLE。

题解

随机生成 $n$ 维列向量 $\vec{x}$,判断 $AB\vec{x} = C\vec{x}$ 是否成立。可在 $O(n^2)$ 时间内完成。

算法出错当且仅当 $(AB-C)\vec{x} = 0$ 而 $AB – C \neq 0$。 假设我们在 $\mathbb{F}_p$ 里做。令 $M = AB – C$, 则 $\vec{x}$ 在 $M$ 的零空间中。仔细想一想 $M$ 的零空间最多 $n-1$ 维,因此出错的概率不会超过$1/p$。

(当然,使用三次方的算法加一些优秀的卡常,也许也能过)

Remark: 

这一算法被称为Freivalds算法,是一种单边错Monte Carlo随机算法。对于整数矩阵,存在确定性的$O(n^2)$的算法判断乘法是否正确。不过由于Freivalds算法非常易于实现,目前实际上仍然大量使用该算法 。


Square

UVA 11542, also available at vjudge

给定 $n$ 个整数的集合你可以生成 $2^n-1$ 个非空子集。求有多少个子集,其中的数之积为完全平方数。

$1 \leq T \leq 30$, $1 \leq n \leq 100$, 所有整数在 1 和 $10^{15}$ 之间。整数的素因子最多为 500。

题解

每个整数的唯一分解序列都看成 $\mathbb{F}_2$ 上的一个的向量,就是要求这些向量构成矩阵的零空间的大小。

发表评论

电子邮件地址不会被公开。 必填项已用*标注