牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共8篇）

矩阵求逆

设逆矩阵为$P$，该矩阵为$A$，单位矩阵为$E$ 则有$P*A=E$ $P*E=P$ 因为做初等行变换等价于被对应的初等矩阵左乘。在$A$化为$E$过程中，对$E$做相同操作，就可以得到$P$。初始化另一个矩阵为单位矩阵，将本矩阵用高斯消元尝试消为单位矩阵。注意该过程不...

数学矩阵线性代数

2019-07-23

0 578

模拟9 题解

A. 随 (rand) 尽量不要重载乘法，真的很慢。 50分算法因为重载乘法被卡常卡成20分，真的很伤。 $void$函数，传入希望存储答案的指针，使用$memcpy$快速传递。 1 void mult(const matrix &a,const matrix &...

组合计数 dp 数学期望矩阵线性代数树上差分原根

2019-07-27

0 338

模拟80 题解

A. 贝尔数这个数据范围，似乎显然是矩阵快速幂。对模数质因数分解就会发现每个质因子只出现一次且很小。所以考虑求出$mod$每个质因子的结果并$crt$合并。题中已经给出了贝尔数在模$p$意义下的一个公式，所以直接保存$p$个贝尔数，矩阵快速幂转移就可以了。 B...

线性代数矩阵 AC自动机 dp 二分图网络流

2019-10-20

0 368

数学专题测试2 题解

A. B $[n=1]=\sum \limits_{d|n} \mu(d)$ 于是考虑用莫比乌斯函数容斥出题意中的$[gcd=1]$。设$f_n$表示$gcd$为$n$的倍数的答案。 $g_n$表示$gcd$为$n$的答案。 $g_1=\sum \limits_{i=1}^n\mu(i)...

矩阵线性代数莫比乌斯函数多项式数列

2020-01-05

0 441

省选模拟47 题解

A. 老夫发现这个问题有点类似二维偏序。所以考虑类似扫描线的做法，枚举第一个维度，同时在第二个维度上用一个数据结构维护答案。所以枚举 $c$ 的取值，然后发现每次的操作是插入一个点。以值域为下标建立一个数据结构，对应的操作就是前缀加下标，询问操作就是全局查询最大值。所以用一个简单...

凸包扫描线分块 dp 矩阵线性代数

2020-03-16

0 378

省选模拟62 题解

A. Fable 虽然没打 noi online，但是大概看了一眼题。其中 T2 就用到了一个结论是：设 $p_{i,k}$ 表示 $i$ 次冒泡排序之后，第 $k$ 个点与之前的点形成的逆序对个数。则有每次冒泡排序之后，$p_{i+1,k}=\max{p_{i,k+1},0}$。 ...

结论题高斯消元多项式 set 矩阵平衡树启发式合并树状数组线性代数

2020-04-04

0 415

省选模拟72 题解

A. 新访问计划 B. 计算几何其实题中这个常数 $c$ 的定义很奇怪，所以大概可以猜想，对于所有的情况都是有解的。然后有这样一个做法，考虑弄一条直线出来，然后把 $n$ 条线段的对应端点都映射到这条直线上。比如坐标系上的点 $(x,y)$ 映射到倾斜角为 $a...

矩阵树定理计算几何分治二分图网络流线性代数凸优化

2020-04-16

0 405

省选模拟93 题解

A. A 肯定是用子序列自动机。然后暴力就是预处理出 DAG 上的路径数然后强行跑。优化的方法类似重链剖分，设 \(f_i\) 表示节点 \(i\) 之后的路径数。 \(f_i\) 等于每个转移边的加和。考虑求出每个节点的重转移。当 \(f_i<inf\)，重转移为每个转移中 \(f\) ...

倍增构造题矩阵期望线性代数

2020-05-11

0 399