Q779的博客

洛谷P2354 [NOI2014] 随机数生成器题解题目链接：P2354 [NOI2014] 随机数生成器题意：小 H 最近在研究随机算法。随机算法往往需要通过调用随机数生成函数（例如 Pascal 中的 random 和 C/C+

2022-10-04 OI

算法

Python 数学模板尝试一下用 Python 写快速幂、exgcd啥的快速幂def qpow(a,b): ans = 1; base = a; while b > 0: if b & 1 :

2022-10-04 OI

瞎搞算法

CF837F Prefix Sums 题解题目链接：CF837F Prefix Sums 题意：考虑函数 $p(x)$，其中 $x$ 是含有 $n$ 个元素的数组 $x_1, \cdots, x_n$，它返回一个新的含有 $n+1$ 个

2022-10-04 OI

算法数学打表

$k$ 阶前缀和公式前缀和对于序列 $a$ ，它的前缀和定义为满足以下条件的序列 $S$ 。 S_n = \sum_{1\le i \le n}a_i特别地，我们通常定义 $S_0=0$ ，但是在本文中不考虑。 $k$ 阶前缀和定义函数

2022-10-04 OI

数学

洛谷P8563 Magenta Potion 题解题目链接：P8563 Magenta Potion 题意：给定一个长为 $n$ 的整数序列 $a$，其中所有数的绝对值均大于等于 $2$。有 $q$ 次操作，格式如下： 1 i k 表

2022-10-03 OI

算法数据结构

洛谷P1232 [NOI2013] 树的计数题解题目链接：P1232 [NOI2013] 树的计数题意：我们知道一棵有根树可以进行深度优先遍历（DFS）以及广度优先遍历（BFS）来生成这棵树的 DFS 序以及 BFS 序。两棵不同的

2022-10-03 OI

算法数学图论

note[7]自己瞎推了一个式子，然后打表发现前几项是 $2^{n-1}$ 。然后改了一改得到这样的式子。 f_0 = 1, ~f_n = \sum_{0 \le i < n} f_i通项为 $f_n = 2^n$ 。然后就试图找到这个

2022-10-03 笔记

数学

生成树计数问题咕咕咕… upd 好家伙，原来有个叫矩阵树定理的东西 QAQ 有空学吧（随手记一下这些奇奇怪怪的东西，说不定会派上用场。以下默认为无向图。 $n$ 个不同的点构成的完全图，其生成树个数为 $n^{n-2}$ 。注意生成树

2022-10-02 OI

数学图论

UOJ460 新年的拯救计划题解题目链接：#460. 新年的拯救计划题意：给定一个 $n$ 阶完全图 $K_n$ ，你需要构造 $K_n$ 的 $m$ 棵不相交的生成树，求 $m$ 的最大值并给出方案。输入格式：共一行，包含一个

2022-10-02 OI

算法图论构造咕咕

洛谷P4180 [BJWC2010] 严格次小生成树题解题目链接：P4180 [BJWC2010] 严格次小生成树题意：给定一张无向连通图，求出它的严格次小生成树。如果最小生成树选择的边集是 $E_M$，严格次小生成树选择的边集是

2022-10-02 OI

算法图论数据结构

洛谷P2478 [SDOI2010]城市规划题解题目链接：P2478 [SDOI2010]城市规划题意：给定一个带点权沙漠（多棵仙人掌），求最大权独立集。此处独立集的定义为集合中任意两个结点的最短路径长度不小于 $3$ （就是隔两

2022-10-01 OI

算法图论 DP 数据结构

CF825G Tree Queries 题解题目链接：CF825G Tree Queries 题意：题目描述：给定一棵包含 $n$ 个节点的树（从 1 到 $n$ 编号），初始所有节点都是白色的。你需要处理以下两种类型的 $n$ 个

2022-10-01 OI

算法数据结构