十二月 26, 2019 · OI 算法
五边形数定理学习笔记
五边形数生成函数即欧拉函数： $\displaystyle{ \varphi(x) = \prod_{n=1}^\infty (1 - x^n) }$
十一月 21, 2019 · OI 题解
「洛谷5655」基础数论函数练习题
给定一个长度为 $n$ 的数组 $\{a_i\}_{i=1}^n$，$Q$ 次询问，每次给定 $l$ 和 $r$ 查询 $\operatorname{lcm}(\{a_i\}_{i=l}^r)$，答案对 $10^9+7$ 取模。 多组数据，$T,n,Q \leq 300,\ a_i \leq 10^{18}$。
九月 27, 2019 · OI 算法
拟阵与拟阵交学习笔记
本文以矩阵交相关内容为主，忽略掉了大部分证明，感兴趣的读者请自行阅读集训队论文。 拟阵的定义记 $M = (S, L)$ 表示一个定义在有限集 $S$ 上，独立集的集合为 $L$ 的拟阵。其中 $L$ 是 $S$ 的一些子集构成的集合。拟阵 $M$ 满足以下公理： (遗传性). 如果 $I \in L, J \subseteq I$，那么 $J \in L$。 (交换性). 如果 $I,J \in L$ 且...
七月 20, 2019 · OI 题解
「雅礼集训2017」PATH
给定 $ n $ 和 $ \{a_i\} $，满足 $ a_0 \geq a_1 \geq \cdots \geq a_{n - 1} \geq 0 $，求出在 $ n $ 维空间中从 $ (0, 0, \ldots, 0) $ 走到 $ (a_0, a_1, \ldots, a_{n - 1}) $，每一步使某一维坐标增加 $ 1 $ 的方案中随机选出一种，满足经过的所有点 $ (x_0, x_1, \ldots, x_{n - 1}) $ 都满足 $ x_0 \geq x_1 \geq \cdots \geq x_{n - 1} $ 的概率，答案模 $ 1004535809 $ 输出。 ...
七月 07, 2019 · OI 题解
「CTT2018」esperar
给定 $n$ 和长度为 $n$ 的数组 $\{a_i \} _{i=1}^n$ ，求满足 $\forall i \in [1, n], c_i | b_i, b_i | a_i$ 并且 $\prod_{i=1}^n c_i^2 \leq \prod_{i=1}^n b_i$ 的 $\{b_i\}_{i=1}^n$ 和 $\{c_i\}_{i=1}^n$ 的方案数。 $n \leq 100,\ a_i \leq 10^9$。
五月 09, 2019 · OI 题解
「CF1053E」Euler tour
给定一棵树的欧拉序，其中被若干位被删除。你可以在被删除的位置填数，要求构造任何一个合法的欧拉序。 $n \leq 5 \times 10^5, |S| = 2n - 1$。
四月 08, 2019 · OI 题解
「HNOI2019」白兔之舞
有一张顶点数为 $(L+1)\times n$ 的有向图。这张图的每个顶点由一个二元组$(u,v)$表示$(0\le u\le L,1\le v\le n)$。这张图不是简单图，对于任意两个顶点 $(u_1,v_1)(u_2,v_2)$，如果 $u_1<u_2$，则从 $(u_1,v_1)$ 到 $(u_2,v_2)$ 一共有 $w[v_1][v_2]$ 条不同的边，如果 $u_1\ge u_2$...