AC. 梦想

线性代数目录下的文章

[ZJOI 2014] 星系调查

题意简述 给定n点m边的简单无向连通图。每个点对应一个二维平面上的坐标。 有q个询问,每次给定u,v,求u,v所有简单路径中,路径权值的最小值。 路径权值定义为,在所有直线中,到路径上所有点对应的坐标的欧几里得距离的平方和的最小值。 1 \le n, q \le 10 ^ 5, m \le n,权值\……
17/03/01 | 暂无评论 | 429阅读 阅读详情

[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} +……
16/05/03 | 暂无评论 | 539阅读 阅读详情

矩阵幂求和

考虑这样一个问题 给定n阶矩阵\textbf{A}(n \le 50),求\textbf{S} = \sum_{k=0}^{m} {\textbf{A} ^ k},(0 \le m \le 10 ^ 9)。 矩阵幂求和?我会二分!其实二分也是也是一种不错的方法,不过还有一种方法。我们来分析一下。 二分法 对次数进行二分,递归求出m/2次的答案,利……
16/03/16 | 暂无评论 | 748阅读 阅读详情

矩阵优化递推

以前一直不会独立分析有关矩阵快速幂优化递推的问题,昨天晚上自己给自己出了一道题。想了许久,似乎明白了一点,那么便记录一下吧。 首先贴上自己给自己出的题(引例): 求下列d阶线性常系数递推关系的第n项0 \le n \le 10 ^ {18},将答案\mod 10 ^ 9 + 7输出。f(x) = \sum_{……
16/03/15 | 1 条评论 | 500阅读 阅读详情

[BZOJ 1013] 球形空间产生器

题目描述 有一个球形空间产生器能够在n维空间中产生一个坚硬的球体。现在,你被困在了这个n维球体中,你只知道球面上n+1个点的坐标,你需要以最快的速度确定这个n维球体的球心坐标,以便于摧毁这个球形空间产生器。 输入格式 第一行是一个整数,n。接下来的n+1行,每行有n个实数……
15/12/22 | 暂无评论 | 486阅读 阅读详情