数学基础向量空间 vector space定义 $(F, V, +, \cdot)$ 为向量空间，其中 $F$ 为域， $V$ 为集合， $V$ 中元素称为向量， $+$ 为向量加法， $\cdot$ 为标量乘法，且运算满足 8 条公理（见维基百科）。 线性无关 linearly independent对于向量空间中 $V$ 上 $n$ 个元素的向量组 $(\mathbf{v_1},\mathbf{v_2},\dots,\mathbf{v_n})$, 若存在不全为 $0$ 的数 $a_i\in F$, 满足 $$a_1\mathbf{v_1}+a_2\mathbf{v_2}+\dots+a_ ...

#[BZOJ1041][HAOI2008] 圆上的整点 给定一个圆 $x^2+y^2=r^2,r\text{ 为整数}$ ，求在圆周上有多少个点的坐标是整数。 $n\leq2\times10^8$ 其实这不是计算几何，而是数论。$$x^2+y^2=r^2\\implies y=\sqrt{(r+x)(r-x)}$$ 令 $d=gcd(r+x,r-x)$, 设 $\displaystyle A=\frac{r-x}{d},B=\frac{r+x}{d}$则 $gcd(A,B)=1$, 即 $A,B$ 互质. 回带得 $y^2=d^2\cdot A\cdot B$由于 $d^2,y^2$ 为完 ...

##图论基本概念###子图子图 subgraph 图 $G=(V,E)$ ，则 $G’=(V’,E’),V’\subseteq V,E’\subseteq E$ 为图 $G$ 的子图。 诱导子图 induced subgraph 图 $G=(V,E)$ ，则 $G’=(V’,E’),V’\subseteq V,E’={(u,v)\mid u,v\in V’,(u,v)\in E}$ 为图 $G$ 的诱导子图。 ###团团 clique 图 $G$ 的一个子图 $G’=(V’,E’)$ ， $G’$ 为关于 $V’$ 的完全图。 极大团 maximal clique 一个团是极大团当且仅当它不是 ...

###[BZOJ1005][HNOI2008] 明明的烦恼 给出一棵树中所有节点的度数（ $-1$ 代表无限制），求可能的树的种类数。 $0<N\leq1000$ 嘛，这是我少有的单独为一道题写的博客，这水题卡了我一晚上，不过不能否认，这道题对现在的我来说确实很有价值，本体需要先推公式，然后分解质因数搞高精。 我们考虑用 $pufer$ 编码来表示一棵树，根据 $pufer$ 编码的性质： 任何一棵无根树都可以表示为长度为 $n-2$ 的串； 一个点的度数是 $d$ ，则它会在串中出现 $d-1$ 次。 我们知道该已知度数的节点组成的串的总长度 $\displaystyle le ...

##状态压缩###[COGS217][USACO Open05] Disease Management $N$ 头奶牛中共有 $D$ 种疾病，选择性地给一些奶牛挤奶，使得挤出牛奶中的疾病总数不超过 $K$ 种，求最多能给多少奶牛挤奶。 $1\leq N\leq100,1\leq D\leq15,1\leq K\leq D$ 1234567891011121314151617181920212223242526272829303132333435363738394041#include<iostream>#include<cstdio>using namespace ...

##介绍 解决树相关问题的算法的时间复杂度经常与树的深度有关，如果能使树的深度变成 $O(log_2n)$ 级别的，那么很多树相关的问题就迎刃而解了，而实现这一目标的一个重要方法就是树分治。 树分治的中心思想就是将一个规模很大的问题分解为几个两个相同形式的子问题，然后进行合并。 我们首先面临的问题就是如何将一颗树最优地划分为两块，而本文所涉及的点分治便是划分方法的其中一种；其思想主要是以一个点为基准，然后处理过此点的链或点对，至于其它的不断分治下去处理。 我们称作为分治基准点的这个点为重心，那么我们肯定希望它的子树大小比较平均，也就是说，我们要找到一个最大子树最小的点作为重心，具体做法很简单， ...

计算几何一类的题目不仅需要精妙的算法设计，还要注意精度等细节问题，常常是比赛中拉分的题目。

所以毕叔叔说：NOI见到计算几何就弃了吧

见到小火车好开心##7.7###壹##7.8###壹 给出 $n,m$ ，求满足 $k\leq n$ 且 $\sum_{i}^{k}\mu(i)=m$ 的一个可能的 $k$ 。 $n<=10^{10}$ 我们直接用线性筛求莫比乌斯函数的话，可以得到 60 分；剩下的分数用杜教筛可以解决。###贰 给出 $n*m$ 的矩阵，有一些格子是特殊的，我们一次可以从底层的相邻列中取出不超过 3 个格子（即为正或反的 “L” 型），求最少要操作几次能把所有的特殊各自取出。 $2\leq n,m\leq2000$ 首先，对结果有影响的只有最上面的特殊格子，我们可以将题目转化成一维的。很明显，我 ...

由于本文涉及的许多专有名词并没有统一的中文译名，所以本文译名与其他资料不尽相同，尽请谅解。##概念 动态树问题, 即要求我们维护一个由若干棵子结点无序的有根树组成的森林. 要求这个数据结构支持对树的分割, 合并, 对某个点到它的根的路径的某些操作, 以及对某个点的子树进行的某些操作. Link-Cut Tree, LCT 是一种能快速解决动态树问题的数据结构。 如果刚刚执行了对这个节点的 access 操作，那么我们称这个点刚刚被访问过。如果在一个节点 u 的子树中， v 刚刚被访问过，那么称 v 是 u 的偏爱子节点 ( Preferred Child ) ；每个点到它的偏爱子节点的边叫 ...

各种平衡树比较| 平衡树 | 附加域 | 平衡性 | 效率 | 编程难度 | 实用性 | 特点 || :—: | :–: | :——: | :——: | :–: | :–: | :–: || Treap | 修正值 | 较好 | 较快 | 易 | 好 | 随机平衡 || Splay | - | 玄学（均摊 中） | 玄学（均摊 中） | 中 | 好 | 灵活易变 || SBT | 子树大小 | 好 | 快 | 中 | 好 | 短小精悍 || BST | 无 ...