线性代数目录下的文章
[ZJOI 2014] 星系调查
题意简述
给定n点m边的简单无向连通图。每个点对应一个二维平面上的坐标。
有q个询问,每次给定u,v,求u,v所有简单路径中,路径权值的最小值。
路径权值定义为,在所有直线中,到路径上所有点对应的坐标的欧几里得距离的平方和的最小值。
1 \le n, q \le 10 ^ 5, m \le n,权值\……
[NOI 2013] 矩阵游戏
题目描述
婷婷是个喜欢矩阵的小朋友,有一天她想用电脑生成一个巨大的n行m列的矩阵(你不用担心她如何存储)。她生成的这个矩阵满足一个神奇的性质:若用F_{i,j}来表示矩阵中第i行第j列的元素,则F_{i,j}满足下面的递推式:\begin{aligned} F_{1,1} &= 1 \\ F_{i,j} &= aF_{i,j-1} +……
矩阵幂求和
考虑这样一个问题
给定n阶矩阵\textbf{A}(n \le 50),求\textbf{S} = \sum_{k=0}^{m} {\textbf{A} ^ k},(0 \le m \le 10 ^ 9)。
矩阵幂求和?我会二分!其实二分也是也是一种不错的方法,不过还有一种方法。我们来分析一下。
二分法
对次数进行二分,递归求出m/2次的答案,利……
矩阵优化递推
以前一直不会独立分析有关矩阵快速幂优化递推的问题,昨天晚上自己给自己出了一道题。想了许久,似乎明白了一点,那么便记录一下吧。
首先贴上自己给自己出的题(引例):
求下列d阶线性常系数递推关系的第n项0 \le n \le 10 ^ {18},将答案\mod 10 ^ 9 + 7输出。f(x) = \sum_{……
[BZOJ 1013] 球形空间产生器
题目描述
有一个球形空间产生器能够在n维空间中产生一个坚硬的球体。现在,你被困在了这个n维球体中,你只知道球面上n+1个点的坐标,你需要以最快的速度确定这个n维球体的球心坐标,以便于摧毁这个球形空间产生器。
输入格式
第一行是一个整数,n。接下来的n+1行,每行有n个实数……