线性代数相关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\) 上的一个的向量,就是要求这些向量构成矩阵的零空间的大小。

发表评论

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