Q779’s Blog

洛谷P2569 [SCOI2010] 股票交易 题解 题目链接：P2569 [SCOI2010] 股票交易 题意： 最近 \(\text{lxhgww}\) 又迷上了投资股票，通过一段时间的观察和学习，他总结出了股票行情的一些规律。 通过一段时间的观察，\(\text{lxhgww}\) 预测到了未来 \(T\) 天内某只股票的走势，第 \(i\) 天的股票买入价为每股 \(AP_i\)，第 \(i\) 天的股票卖出价为每股 \(BP_i\)（数据保证对于每个 \(i\)，都有 \(AP_i \geq BP_i\)），但是每天不能无限制地交易，于是股票交易所规定第 \(i\) 天的一次买入至多只能购买 \(AS_i\) 股，一次卖出至多只能卖出 \(BS_i\) 股。 另外，股票交易所还制定了两个规定。为了避免大家疯狂交易，股票交易所规定在两次交易（某一天的买入或者卖出均算是一次交易）之间，至少要间隔 \(W\) 天，也就是说如果在第 \(i\) 天发生了交易，那么从第 \(i+1\) 天到第 \(i+W\) 天，均不能发生交易。同时，为了避免垄断，股票交易所还规定在任何时间，...

CF1808E3 Minibuses on Venus (hard version) 题解 题目链接：Minibuses on Venus (hard version) 题意： 给定 \(n,k,m\) ，定义序列 \(\{a_i\}_{i=1}^n\) 的值域为 \([0,k)\) ，即 \(\forall i, ~a_i \in[0,k)\) 。 称一个序列 \(a\) 是幸运的，当且仅当存在至少一个 \(p~(1\le p \le n)\) 使得 \[ \sum_{i=1}^na_i - a_p\equiv a_p \pmod{k} \] 求幸运序列的总方案数模 \(m\) 的结果。 输入格式： 一行，三个整数 \(n,k,m\) 。 输出格式： 一行，即答案。 数据范围： \(1 \le n \le 10^{18},~1\le k \le 2000,~10^8 \le m \le 10^9\) 。 记 \(s = \sum_{i=1}^n a_i\) ，考虑问题的反面，即 \(s \not\equiv 2a_i \pmod{k}\) 的序列 考虑枚举 \(s \in ...

同余的基本性质 一、定义 设整数 \(m \ne 0\) 。若 \(m \mid (a - b)\) ，则称 \(m\) 为模数（模）， \(a\) 同余于 \(b\) 模 \(m\) ，\(b\) 是 \(a\) 对模 \(m\) 的剩余，记作 \(a \equiv b \pmod{m}\) 。 否则 \(a\) 不同余 \(b\) 模 \(m\) ，\(b\) 不是 \(a\) 对模 \(m\) 的剩余，记作 \(a \not\equiv b \pmod{m}\) 。 这样的等式称为模 \(m\) 的同余式，简称同余式。 根据整除的性质，上述同余式也等价于 \(a \equiv b \pmod{(-m)}\) 故未特别注明的情况，默认模数为正整数。 二、性质 同余是等价关系，即同余具有 自反性：\(a\equiv a\pmod m\) 对称性：若 \(a\equiv b\pmod m\)，则 \(b\equiv a\pmod m\) 传递性：若 \(a\equiv b\pmod m,b\equiv c\pmod m\)，则 \(a\equiv c\pmod m\) ...

【生物】纺锤丝和星射线的区别 纺锤体在动物细胞和高等植物细胞中有差异。 动物细胞的纺锤体两端有星状体，每个星状体的中间有中心体，称为有星纺锤体。 高等植物细胞的纺锤体两端没有星状体，呈桶状，称为无星纺锤体。 组成纺锤体的丝状结构称为纺锤丝。 纺锤丝共四种，即连续丝、牵引丝、中间丝和星体丝（即星射线）。 连续丝是由一极与另一极相连的纺锤丝。 牵引丝又称染色体丝，是着丝点与一极相连的纺锤丝。 中间丝不与两极相连，也不与着丝点相连，是在后期于两组染色体之间出现的纺锤丝 星体丝又称星射线，由两极的中心体射出，它只存在于有星纺锤体的细胞内。 各种纺锤丝都由微管蛋白组成。 动/植物细胞共有的纺锤丝是染色体丝和连续丝，动物细胞特有的是中间丝和星射线。 题外话： 因为找不到翻译所以直接翻译了维基百科的图。

洛谷P4721 【模板】分治 FFT 题解 题目链接：P4721 【模板】分治 FFT 题意： 给定序列 \(g_{1\dots n - 1}\)，求序列 \(f_{0\dots n - 1}\)。 其中 \[ f_i=\sum_{j=1}^if_{i-j}g_j \] 边界为 \(f_0=1\)。 答案对 \(998244353\) 取模。 输入格式： 第一行一个整数 \(n\) 。 第二行 \(n-1\) 个整数 \(g_{1\dots n - 1}\)。 输出格式： 一行 \(n\) 个整数，表示 \(f_{0\dots n - 1}\) 对 \(998244353\) 取模后的值。 数据范围： \(2\leq n\leq 10^5\)，\(0\leq g_i<998244353\)。 本题可以通过多项式求逆解决，不过这就体现不出「分治 FFT 模板题」的意义了。 分治 FFT/分治NTT 主要利用的是 CDQ 分治的思想。 先求出 \([l,\,\mathrm{mid}-1)\) 的答案（即 \(f\) ），可以发现这部分对于 \([\mathrm{mid},r...

洛谷P5787 【模板】线段树分治 题解 题目链接：P5787 二分图 /【模板】线段树分治 题意： cxy 有一个 \(n\) 个节点的图。 因为 cxy 是 cxy，所以在 \(k\) 时间内有 \(m\) 条边会出现后消失。 cxy 要求出每一时间段内这个图是否是二分图。 这么简单的问题 cxy 当然会做了，于是她想考考你。 输入格式： 第一行三个整数 \(n,m,k\)。 接下来 \(m\) 行，每行四个整数 \(x,y,l,r\)，表示有一条连接 \(x,y\) 的边在 \(l\) 时刻出现 \(r\) 时刻消失。 输出格式： 共 \(k\) 行，第 \(i\) 行一个字符串 Yes 或 No，表示在第 \(i\) 时间段内这个图是否是二分图。 数据范围： \(1\le n,k \le 10^5,~1 \le m \le 2\times 10^5,~1 \le x,y \le n,~0 \le l \le r \le k\)。 本题是线段树分治的模板题。 线段树分治其实非常简单。考虑对时间轴建立线段树，每个节点维护这段区间存在的边集。 因为如果区间 \([l,r]\...

洛谷P5495 【模板】Dirichlet 前缀和 题解 题目链接：P5495 【模板】Dirichlet 前缀和 题意： 给定一个长度为 \(n\) 的数列 \(a_1,a_2,a_3,\dots,a_n\)。 现在你要求出一个长度为 \(n\) 的数列 \(b_1,b_2,b_3,\dots,b_n\)，满足 \[ b_k=\sum_{i\mid k}a_i \] 由于某些神秘原因，这里的 \(b_k\) 要对 \(2^{32}\) 取模。 输入格式： 为了避免过大的输入，本题的输入使用随机数生成器。 输入中只有一行两个整数 \(n,\mathrm{seed}\)。其中 \(\mathrm{seed}\) 为 \(32\) 位无符号整数，用来生成数据。 接下来，你要调用 \(n\) 次随机数生成器，分别生成 \(a_1\sim a_n\)。随机生成器见原题链接。 输出格式： 为了避免过大的输出，你只需输出一个 \(32\) 位无符号整数，表示所有 \(b_i\) 的异或和。 数据范围： \(1\leq n\leq 2\times 10^7\)，\(0\leq \mathrm...

洛谷P6097 【模板】子集卷积 题解 题目链接：P6097 【模板】子集卷积 题意： 给定两个长度为 \(2^n\) 的序列 \(a_0,a_1,\cdots,a_{2^n-1}\) 和 \(b_0,b_1,\cdots,b_{2^n-1}\) 你需要求出一个序列 \(c_0,c_1,\cdots,c_{2^n-1}\)，其中 \(c_k\) 满足： \[ c_k=\sum_{(i \lor j) = k,~(i \land j) = 0} a_i b_j \] 其中 \(\lor\) 表示按位或，\(\land\) 表示按位与。答案对 \(10^9+9\) 取模。 输入格式： 第一行输入一个正整数 \(n\) ，表示集合的大小。 第二行有 \(2^n\) 个整数，描述了 \(a\)。 第三行有 \(2^n\) 个整数，描述了 \(b\)。 输出格式： 输出一行 \(2^n\) 个整数，表示 \(c\)。 数据范围： \(1\le n\le 20\)，\(0\le a_i,b_i< 10^9+9\)。 才发现这个 \(2^n-1\) 个数就是 \(n\) 个元素的所有...

洛谷P7155 [USACO20DEC] Spaceship P 题解 题目链接：P7155 [USACO20DEC] Spaceship P 题意： Bessie 在一张含 \(n\) 个结点的有向图上遍历，站在某个结点上时，她必须按下自己手中 \(m\) 个按钮中处于激活状态的一个才能走向其他结点或终止遍历（不能原地等待）。初始时，所有按钮都处于激活状态，按下 \(i\) 号按钮时，\(i\) 号按钮变为非激活状态，所有编号小于 \(i\) 的按钮被激活。 给定 \(q\) 组形如 \((b_s,s,b_t,t)\) 的询问，求 Bessie 从 \(s\) 出发，第一步按 \(b_s\) 按钮，到 \(t\) 终止遍历，且最后一步按 \(b_t\) 按钮的遍历方案数（遍历顺序或按键不同，方案则不同）。 输入格式： 输入的第一行包含 \(n,m,q\)。 接下来 \(n\) 行长度为 \(n\) 的 \(01\) 串，表示图的邻接矩阵。 接下来 \(q\) 行 \((b_s,s,b_t,t)\) 询问，变量含义见题意。 输出格式： 对于每个询问，给出答案模 \(10^9 +...

洛谷P2495 [SDOI2011] 消耗战 题解 题目链接：P2495 [SDOI2011] 消耗战 题意： 在一场战争中，战场由 \(n\) 个岛屿和 \(n-1\) 个桥梁组成，保证每两个岛屿间有且仅有一条路径可达。现在，我军已经侦查到敌军的总部在编号为 \(1\) 的岛屿，而且他们已经没有足够多的能源维系战斗，我军胜利在望。已知在其他 \(k\) 个岛屿上有丰富能源，为了防止敌军获取能源，我军的任务是炸毁一些桥梁，使得敌军不能到达任何能源丰富的岛屿。由于不同桥梁的材质和结构不同，所以炸毁不同的桥梁有不同的代价，我军希望在满足目标的同时使得总代价最小。 侦查部门还发现，敌军有一台神秘机器。即使我军切断所有能源之后，他们也可以用那台机器。机器产生的效果不仅仅会修复所有我军炸毁的桥梁，而且会重新随机资源分布（但可以保证的是，资源不会分布到 \(1\) 号岛屿上）。不过侦查部门还发现了这台机器只能够使用 \(m\) 次，所以我们只需要把每次任务完成即可。 输入格式： 第一行一个整数 \(n\)，表示岛屿数量。 接下来 \(n-1\) 行，每行三个整数 \(u,v,w\) ，表示...

洛谷P7735 [NOI2021] 轻重边 题解 题目链接：P7735 [NOI2021] 轻重边 题意： 小 W 有一棵 \(n\) 个结点的树，树上的每一条边可能是轻边或者重边。 在所有操作开始前，树上所有边都是轻边。 接下来你需要对树进行 \(m\) 次操作，操作有以下两种： 给定两个点 \(a\) 和 \(b\)，首先对于 \(a\) 到 \(b\) 路径上的所有点 \(x\)（包含 \(a\) 和 \(b\)），你要将与 \(x\) 相连的所有边变为轻边。然后再将 \(a\) 到 \(b\) 路径上包含的所有边变为重边。 给定两个点 \(a\) 和 \(b\)，你需要计算当前 \(a\) 到 \(b\) 的路径上一共包含多少条重边。 输入格式： 本题有多组数据，输入数据第一行一个正整数 \(T\)，表示数据组数。对于每组数据： 第一行包含两个整数 \(n\) 和 \(m\)，其中 \(n\) 表示结点数量，\(m\) 表示操作数量。 接下来 \(n - 1\) 行，每行包含两个整数 \(u,v\)，表示树上的一条边。 接下来 \(m\) 行，每行包含三个整数 \(...

洛谷P7984 [USACO21DEC] Tickets P 题解 题目链接：P7984 [USACO21DEC] Tickets P 题意： Bessie 正在参加远足旅行！她当前正在旅行的路线由编号为 \(1\ldots N\)（\(1\le N\le 10^5\)）的 \(N\) 个检查点组成。 有 \(K~(1\le K\le 10^5)\) 张票可供购买。第 \(i\) 张票可以在检查站 \(c_i~(1\le c_i\le N)\) 以 \(p_i~(1\le p_i\le 10^9)\) 的价格购得，并且可以用其进入所有检查站 \([a_i,b_i]\)（\(1\le a_i\le b_i\le N\)）。在进入任何检查站之前，Bessie 必须已购买一张允许其进入该检查站的票。一旦 Bessie 可以前往某一检查站，她就可以在未来的任何时候回到该检查站。 对于每一个 \(i\in [1,N]\)，如果 Bessie 最初只能进入检查点 \(i\)，输出使得可以进入检查点 \(1\) 和 \(N\) 所需的最低总价。如果无法这样做，输出 \(-1\)。 输入格式：...