Notes on Module 逆元对于模意义下的除法,$a/x \equiv b \pmod m \Leftrightarrow a \times x^{-1} \equiv b \pmod m$,则称$x^{-1}$为$x$在模$m$意义下的逆元。 关于逆元的求法可以参考 Notes on Multiplicative Inverse。 考虑线性同余方程$ax \equiv b \pmod m$,有 $$(a 2017-07-07 OI > Number Theory #Prime #Combinatorics #Chinese Remainder Theorem #Lucas's Theorem #Multiplicative Inverse #Note
Legacy 题目描述Rick and his co-workers have made a new radioactive formula and a lot of bad guys are after them. So Rick wants to give his legacy to Morty before bad guys catch them. There are n planets in their 2017-07-05 OI > Data Structure #Shortest Path #Segment Tree
Notes on Graph Theory Matrix-Tree矩阵的秩、迹、特征值、特征向量 对角化 $G \rightarrow M, M^k, k \in N^*$. $G=k_n$. Hoffman-Singleton$G, \Delta-free, C_4-free, r-regular$. $(1) |v| \ge r^2+1$. $(2) r, |v|=r^2+1$. $G \rightarrow A, 2017-07-05 OI > Number Theory #Note #Kirchhoff's Theorem
Notes on Math Theory Lucas$n=(a_ka_{k-1}a_{k-2}\ldots a_0)_p, \ m=(b_kb_{k-1}b_{k-2}\ldots b_0)_p, \ {n \choose m} \equiv \prod_{i=0}^k {a_i \choose b_i} \pmod p$. $n!$中$p$的次数$=\sum_{i=1}^{\infty} 2017-07-04 OI > Number Theory #Prime #Lucas's Theorem #Note #Lagrange Interpolation Polynomial
Query on the Subtree 题目描述Bobo has a tree, whose vertices are conveniently labeled by $1, 2, \ldots, n$. At the very begining, the $i$-th vertex is assigned with weight $w_i$. There are $q$ operations. Each operations are 2017-07-03 OI > Common Skill #Lowest Common Ancestor #Binary Indexed Tree #Tree #Centroid Decomposition #Inclusion-Exclusion Principle
Digit Tree 题目描述ZS the Coder has a large tree. It can be represented as an undirected connected graph of $n$ vertices numbered from $0$ to $n-1$ and $n-1$ edges between them. There is a single nonzero digit writt 2017-07-02 OI > Number Theory #Multiplicative Inverse #Tree #Centroid Decomposition
Notes on Multiplicative Inverse 扩展欧几里得算法求$a$对模$b$的逆当$(a, b)=1$时,有 $$\exists x, y \in Z, \ ax+by=1$$ 扩展欧几里得算法证明如下: 设$a \gt b$。 当$b=0$时,有 $$a \times 1+b \times 0=a=(a, b)=1$$ 此时$x=1, \ y=0$。 当$ 2017-07-01 OI > Number Theory #GCD-LCM #Multiplicative Inverse #Note
D Tree 题目描述There is a skyscraping tree standing on the playground of Nanjing University of Science and Technology. On each branch of the tree is an integer (The tree can be treated as a connected graph with 2017-07-01 OI > Number Theory #Multiplicative Inverse #Tree #Centroid Decomposition
Tree 题目描述Give a tree with $n$ vertices, each edge has a length (positive integer less than $1001$). Define $dist(u, v)= \text{The min distance between node} \ u \ \text{and} \ v$. Give an integer $k$, 2017-07-01 OI > Common Skill #Self-Balancing Binary Search Tree #Tree #Centroid Decomposition
Complete the Graph 题目描述ZS the Coder has drawn an undirected graph of $n$ vertices numbered from $0$ to $n-1$ and m edges between them. Each edge of the graph is weighted, each weight is a positive integer. The next day, 2017-06-30 OI > Graph Theory #Shortest Path