目录 三维几何1. 点和向量 三维几何2. 平面 三维几何3. 直线 一些废话 三维几何系列文章将会尽可能全面地介绍三维计算几何的基础知识，并简单地引入部分重要的计算机图形学内容，希望能够顺利更新完。由于这些文章本质上是我的学习笔记，没有审稿人，如有错误请务必指出！ 引用 Geometry in competitive programming, V…

这个项目是对XCPC竞赛中常用（？）算法以及常见模型的总结，将会长期更新。具体内容请查看GitHub：  GitHubst1vdy/Algorithm-Library  

本文参考 Codeforces edu线段树教程 ac-library lazy segtree 本文的代码实现基于递归式线段树，下标从 $1$ 开始，维护的区间是 $[l,r]$（左闭右闭）；但是引用的codeforces教程默认区间是 $[l,r)$（左闭右开）。 区间修改+单点查询 区间加+单点查询 给定一个 n 个元素的数组 a，处理以下两…

本文内容来源于论文An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale。 本文前置：Transformer。 Vision Transformer所做的工作主要是将transformer架构引入到了计算机视觉领域（论文中是图像分类任务），给出了图像怎么转…

本文内容主要来源于Transformer原始论文、The Annotated Transformer和CMU Advanced NLP Fall 2024 (4): Attention and Transformers。 Model Architecture 大多数有竞争力的神经序列转换模型（Neural Sequence Transduction…

本文内容主要来源于"Computational Geometry - Algorithms and Applications"书中第8.2章和11.4章。 对偶变换 在二维几何中，对偶性是一种将点和线之间的关系互换的概念。 在点-线对偶中，平面上的每一条直线可以映射为一个点，反之亦然。具体地，点 $(p_x,p_y)$ 的对偶是直线 $y+p_y=…

本文原始论文：链接。 符号定义 $\lfloor x\rfloor$ 表示小于等于 $x$ 的最大整数；$\{x\}=x-\lfloor x\rfloor$，即 $x$ 的小数部分；$\%$ 表示取模。 线段上的格点数 如果你熟悉exgcd和线性同余方程，那么可以直接跳过本节。 定义1 设 $x_1,y_1,x_2,y_2$ 为有理数，定义 $L(…

AtCoder Beginner Contest 371题解 E - I Hate Sigma Problems 定义函数 $f(l,r)$ 表示 $A[l],A[l+1],\cdots,A[r]$ 中不同的元素个数，求$$\sum_{i=1}^N\sum_{j=i}^N f(i,j).$$ 其实就是求数组 $A$ 中所有区间的元素种类数。可以通过…

点值表示法 对于一个 $n-1$ 阶多项式 $P(x)=a_0+a_1x+a_2x^2+\cdots+a_{n-1}x^{n-1}$，如果我们已知一个点集 $S:\{(x_0,y_0),(x_1,y_1),\cdots,(x_{n-1},y_{n-1})\}$，点集 $S$ 中的所有点都满足 $y_i=P(x_i)$，且 $x_i(i=0,1,\c…

傅里叶级数的复数形式 推导 在傅里叶级数章节中，我们已知一个周期为 $2l$ 的周期函数可以展开为 $$f(x) = a_0 + \sum_{i=1}^{\infty}a_i \cos \frac{i\pi x}{l} + \sum_{i=1}^{\infty} b_i\sin \frac{i\pi x}{l}$$ 为了方便起见，我们作如下定义：常…

直线 定义 一般式 不像二维几何中，直线 $l$ 可以直接用一个方程 $ax+by=c$ 简单地表示，三维几何中 $ax+by+cz=d$ 表示一个平面。而直线可以表示为两个平面的交，即方程组 $$l:\begin{cases}\Pi_1: a_1x+b_1y+c_1z=d_1\\\Pi_2: a_2x+b_2y+c_2z=d_2\\\end{ca…