Q779’s Blog

LightOJ1341 Aladdin and the Flying Carpet 题解 题目链接：Aladdin and the Flying Carpet 题意： \(Q\) 组询问，每组询问给定 \(n,m\) ，求有多少个无序对 \((a,b)\) 满足 \[ a \times b = n \,\land\, a,b \ge m \] \(1 \le m\le n \le 10^{12}\) 关键词：因数枚举 很简单，枚举 \(n\) 的全部因数然后判断即可，直接暴力做是 \(\mathcal{O}(Q\sqrt{n})\) 的。 可以用 \(\mathtt{Pollard\ Rho}\) 算法优化到期望 \(\mathcal{O}(Qn^{\frac{1}{4}})\) 但是没必要这么麻烦，考虑一种预处理的方法。 我们可以将 \(n\) 写成唯一分解的形式，即 \(n = p_1^{t_1}p_2^{t_2}\cdots p_k^{t_k}\) 这里素因子可以用线性筛预处理，复杂度为 \(\mathcal{O}(\sqrt{N})\) 。 显然 \(n\) 的因数 ...

洛谷P2354 [NOI2014] 随机数生成器 题解 题目链接：P2354 [NOI2014] 随机数生成器 题意： 小 H 最近在研究随机算法。随机算法往往需要通过调用随机数生成函数（例如 Pascal 中的 random 和 C/C++中的 rand）来获得随机性。事实上，随机数生成函数也并不是真正的“随机”，其一般都是利用某个算法计算得来的。 比如，下面这个二次多项式递推算法就是一个常用算法： 算法选定非负整数 \(x_0,a,b,c,d\) 作为随机种子，并采用如下递推公式进行计算。 对于任意 \(i \ge 1,x_i=(a \times x_{i-1}^2+b \times x_{i-1}+c)\bmod d\) 这样可以得到一个任意长度的非负整数数列\(\{x_i\},i \ge 1\)，一般来说，我们认为这个数列是随机的。 利用随机序列 \({xi},i\ge\)，我们还可以采用如下算法来产生一个 \(1\) 到 \(K\) 的随机排列\(\{ T_i \},~i=1 ... k\)： 1、初始设 \(T\) 为 \(1\) 到 \(K\) 的递增序列； 2、...

Python 数学模板 尝试一下用 Python 写快速幂、exgcd啥的 快速幂 def qpow(a,b): ans = 1; base = a; while b > 0: if b & 1 : ans *= base; base *= base; b >>= 1; return ans; n = int(input()); m = int(input()); print(qpow(n,m)); 输入： 5 4 输出： 625 最大公约数 def gcd(a,b): if b == 0: return a; return gcd(b, a%b); a = int(input()); b = int(input()); print(gcd(a,b)); 输入： 12 16 输出： 4 Exgcd 咕咕咕…

CF837F Prefix Sums 题解 题目链接：CF837F Prefix Sums 题意： 考虑函数 \(p(x)\)，其中 \(x\) 是含有 \(n\) 个元素的数组 \(x_1, \cdots, x_n\)，它返回一个新的含有 \(n+1\) 个元素的数组 \(y_0,y_1, \cdots, y_n\)，满足 \(y_k = \sum\limits_{i=1}^k x_i\)。 你有一个无限的数组序列 \(A^0, A^1, A^2, \cdots\)，其中 \(A^0\) 由输入给出，且对于每个 \(i \geq 1\)，都有 \(A^i = p \left( A^{i-1} \right)\)。你还有一个正整数 \(m\)，你需要找到最小的 \(i\)，使得 \(A^i\) 中存在 \(\ge m\) 的项。 输入格式： 第一行包含两个正整数 \(n, m~(2 \leq n \leq 2 \times 10^5,0\le m \leq 10^{18})\)，其中 \(n\) 表示数组 \(A_0\) 的大小。 第二行包含 \(n\) 个正整数 \(a_1,...

\(k\) 阶前缀和公式 前缀和 对于序列 \(a\) ，它的前缀和定义为满足以下条件的序列 \(S\) 。 \[ S_n = \sum_{1\le i \le n}a_i \] 特别地，我们通常定义 \(S_0=0\) ，但是在本文中不考虑。 \(k\) 阶前缀和 定义函数 \(f : a \to S\) 为序列 \(a\) 到它的前缀和 \(S\) 的映射。 则序列 \(a\) 的 \(k\) 阶前缀和为 \(f^k(a)~(k \ge 1)\) 。通俗地说，就是对 \(a\) 做了 \(k\) 次前缀和。 \(k\) 阶前缀和公式 记序列 \(a\) 的 \(k\) 阶前缀和为 \(S_k\) ，\(S_k\) 的第 \(i\) 项为 \(S_{k,i}\) ，则 \[ S_{k,i} = \sum_{1 \le j \le i} \binom{k + i - j - 1}{k-1}a_j \] 证明： 考虑一个元素 \(x\) 在位置 \(1\) 时对第 \(i\) 次前缀和的贡献。 设 \(f_{i,j}\) 表示第 \(i\) 次前缀和的第 \(j\) 项的系数，...

洛谷P8563 Magenta Potion 题解 题目链接：P8563 Magenta Potion 题意： 给定一个长为 \(n\) 的整数序列 \(a\)，其中所有数的绝对值均大于等于 \(2\)。有 \(q\) 次操作，格式如下： 1 i k 表示将 \(a_i\) 修改为 \(k\)。保证 $k $ 的绝对值大于等于 \(2\)。 2 l r 考虑 \([l,r]\) 的子区间（包括本身）中乘积最大的的区间乘积 \(M\)。如果 \(M>2^{30}\)，输出 Too large，否则输出 \(M\)。特别地，空区间的元素乘积定义为 \(1\)。 输入格式： 第一行两个正整数表示 \(n,q\)。 第二行输入 \(n\) 个整数表示 \(a_i\)。 接下来 \(q\) 行，每行三个整数表示一次询问，格式见上。 输出格式： 对于每次操作2，输出一行表示询问的答案。 数据范围： 对于所有的数据，\(2\le |a_i|,|k| \le 10^9\)，\(1 \le n,q \le 2\times 10^5\)，\(1 \le l \le r \le n\)。 ...

洛谷P1232 [NOI2013] 树的计数 题解 题目链接：P1232 [NOI2013] 树的计数 题意： 我们知道一棵有根树可以进行深度优先遍历（DFS）以及广度优先遍历（BFS）来生成这棵树的 DFS 序以及 BFS 序。两棵不同的树的 DFS 序有可能相同，并且它们的 BFS 序也有可能相同，例如下面两棵树的 DFS 序都是 1 2 4 5 3，BFS 序都是 1 2 3 4 5。 现给定一个 DFS 序和 BFS 序，我们想要知道，符合条件的有根树中，树的高度的平均值。即，假如共有 \(K\) 棵不同的有根树具有这组 DFS 序和 BFS 序，且他们的高度分别是 \(h_1, h_2, \ldots, h_K\)，那么请你输出： \[ \frac{h_1+h_2+\ldots+h_K}K \] 输入格式： 第一行包含 \(1\) 个正整数 \(n\)，表示树的节点个数。 第二行包含 \(n\) 个正整数，是一个 \(1 \ldots n\) 的排列，表示树的 DFS 序。 第三行包含 \(n\) 个正整数，是一个 \(1 \ldots n\) 的排列，表示树的 B...

note[7] 自己瞎推了一个式子，然后打表发现前几项是 \(2^{n-1}\) 。 然后改了一改得到这样的式子。 \[ f_0 = 1, ~f_n = \sum_{0 \le i < n} f_i \] 通项为 \(f_n = 2^n\) 。然后就试图找到这个式子的意义。 实际上这个东西的一种意义是 \(n\) 元集的子集个数 证明：这个递推式就是在枚举每个集合的最大元素。\(\square\) （QAQ.jpg

生成树计数问题 咕咕咕… upd 好家伙，原来有个叫矩阵树定理的东西 QAQ 有空学吧（ 随手记一下这些奇奇怪怪的东西，说不定会派上用场。 以下默认为无向图。 \(n\) 个不同的点构成的完全图，其生成树个数为 \(n^{n-2}\) 。注意生成树没有根节点。 另一种说法为：一个带标号的 \(n\) 个结点的完全图的生成树个数有 \(n^{n−2}\) 个。 证明：Cayley公式，见浅谈 Prüfer 序列 \(n\) 个不同的点构成的完全图，其有根生成树的个数为 \(n^{n-1}\) 。 见上一条，枚举哪个点是根，即可得到。 \(n\) 个无区别点构成的完全图，其不相交生成树的个数为 \(\left\lfloor\frac{n}{2}\right\rfloor\) 。 见 UOJ460 新年的拯救计划 题解

UOJ460 新年的拯救计划 题解 题目链接：#460. 新年的拯救计划 题意： 给定一个 \(n\) 阶完全图 \(K_n\) ，你需要构造 \(K_n\) 的 \(m\) 棵不相交的生成树，求 \(m\) 的最大值并给出方案。 输入格式： 共一行，包含一个正整数 \(n (3\le n\le 2000)\)，表示图的阶数。 输出格式： 输出的第一行是一个正整数 \(m\)，表示生成树的个数。 接下来 \(m\) 行，每行 \(2(n−1)\) 个数，描述一棵生成树，其中第 \(2i−1\) 和第 \(2i\) 个数表示树中的 一条边。 你需要保证你输出的 \(m\) 个子图为 \(K_n\) 的 \(m\) 棵不相交生成树。 如果有多组解，输出任意一组均可。 还在咕咕咕，因为不是很懂。。 口糊了一下dp然后发现方案数是可以 \(\mathcal{O}(1)\) 的，结果不会构造（悲。然后瞄了眼题解发现dp是错的（悲*2 直接说正解吧，方案数为 \(\left\lfloor\frac{n}{2}\right\rfloor\) 。 证明：首先 \(n\) 阶完全图有 \(\...

洛谷P4180 [BJWC2010] 严格次小生成树 题解 题目链接：P4180 [BJWC2010] 严格次小生成树 题意： 给定一张无向连通图，求出它的严格次小生成树。 如果最小生成树选择的边集是 \(E_M\)，严格次小生成树选择的边集是 \(E_S\)，那么需要满足： \[ \sum_{(u,v) \in E_M}w(u,v)<\sum_{(u,v) \in E_S}w(u,v) \] 输入格式： 第一行包含两个整数 \(N\) 和 \(M\)，表示无向图的点数与边数。 接下来 \(M\) 行，每行 \(3\) 个数 \(x,y,z\) 表示，点 \(x\) 和点 \(y\) 之间有一条边，边的权值为 \(z\)。 输出格式： 包含一行，仅一个数，表示严格次小生成树的边权和。 数据中无向图不保证无自环 对于 \(100\%\) 的数据， \(N\le 10^5\)，\(M\le 3\times10^5\)，边权 \(\in [0,10^9]\)，数据保证必定存在严格次小生成树。 欠了快一年的题，现在来写好像挺适合的。 注意，「\(\Sigma\) 次小 ≤ \(...

洛谷P2478 [SDOI2010]城市规划 题解 题目链接：P2478 [SDOI2010]城市规划 题意： 给定一个带点权沙漠（多棵仙人掌），求最大权独立集。 此处独立集的定义为集合中任意两个结点的最短路径长度不小于 \(3\) （就是隔两个结点） 独立集的权值定义为独立集中所有的点的权值的和。 数据范围： \(n\le 10^6,m\le 2\times 10^6\)，且点权 \(0\le h_i \le 1000\)。 提示： 原题给出的是点仙人掌组成的沙漠。 点仙人掌的定义为：每个点至多存在于一个简单环内的无向连通图。 边仙人掌的定义为：每条边至多存在于一个简单环内的无向连通图。 考虑这样一张图 (1,2) (1,3) (2,3) (3,4) (3,5) (4,5) 。它就是边仙人掌，而不是点仙人掌。 仙人掌dp套dp神题，想了我大概 \(5\) 个小时（其实是沙漠） 我们可以用 \(\mathtt{Tarjan}\) 找环，然后分别考虑树上dp和环上dp。 设 \(f_{i,0/1/2}\) ，则 \(f_{i,0}\) 表示选了 \(i\) ， \(i\) 所...