洛谷P6097 【模板】子集卷积 题解
洛谷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 题解 题目链接: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] 消耗战 题解 & 虚树模板 题目链接:P2495 [SDOI2011] 消耗战 题意: 在一场战争中,战场由 \(n\) 个岛屿和 \(n-1\) 个桥梁组成,保证每两个岛屿间有且仅有一条路径可达。现在,我军已经侦查到敌军的总部在编号为 \(1\) 的岛屿,而且他们已经没有足够多的能源维系战斗,我军胜利在望。已知在其他 \(k\) 个岛屿上有丰富能源,为了防止敌军获取能源,我军的任务是炸毁一些桥梁,使得敌军不能到达任何能源丰富的岛屿。由于不同桥梁的材质和结构不同,所以炸毁不同的桥梁有不同的代价,我军希望在满足目标的同时使得总代价最小。 侦查部门还发现,敌军有一台神秘机器。即使我军切断所有能源之后,他们也可以用那台机器。机器产生的效果不仅仅会修复所有我军炸毁的桥梁,而且会重新随机资源分布(但可以保证的是,资源不会分布到 \(1\) 号岛屿上)。不过侦查部门还发现了这台机器只能够使用 \(m\) 次,所以我们只需要把每次任务完成即可。 输入格式: 第一行一个整数 \(n\),表示岛屿数量。 接下来 \(n-1\) 行,每行三个整数 \(...
洛谷P7735 [NOI2021] 轻重边 题解
洛谷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 题解 题目链接: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\)。 输入格式:...
洛谷P4331 [BalticOI 2004] Sequence 数字序列 题解
洛谷P4331 [BalticOI 2004] Sequence 数字序列 题解 题目链接:P4331 [BalticOI 2004] Sequence 数字序列 题意: 给定一个整数序列 \(a_1, a_2, \cdots , a_n\),求出一个递增序列 \(b_1 < b_2 < ··· < b_n\), 使得序列 \(a_i\) 和 \(b_i\) 的各项之差的绝对值之和 \(|a_1 - b_1| + |a_2 - b_2| + \cdots + |a_n - b_n|\) 最小。 输入格式: 第一行为数字 \(n (1≤n≤10^6)\),接下来一行共有 \(n\) 个数字,表示序列 \(a_i (0≤a_i≤2^{31}-1)\)。 输出格式: 第一行输出最小的绝对值之和。 第二行输出序列 \(b_i\),若有多种方案,只需输出其中一种。 数据范围: \(1\le n\le 10^6 , 0\le a_i\le 2^{31}-1\); 本题可以转化为另一个模型,即 给定序列 \(a_i\) ,每次可以将任意元素加 \(1\) 或减 \(1\)...
洛谷P3270 [JLOI2016] 成绩比较 题解
洛谷P3270 [JLOI2016] 成绩比较 题解 题目链接:P3270 [JLOI2016] 成绩比较 题意: G 系共有 \(N\) 位同学,\(M\) 门必修课。这 \(N\) 位同学的编号为 \(0\) 到 \(N-1\) 的整数,其中 B 神的编号为 \(0\) 号。这 \(M\) 门必修课编号为 \(0\) 到 \(M-1\) 的整数。一位同学在必修课上可以获得的分数是 \(1\) 到 \(U_i\) 中的一个整数。 如果在每门课上 A 获得的成绩均小于等于 B 获得的成绩,则称 A 被 B 碾压。在 B 神的说法中,G 系共有 \(K\) 位同学被他碾压(不包括他自己),而其他 \(N-K-1\) 位同学则没有被他碾压。D 神查到了 B 神每门必修课的排名。 这里的排名是指:如果 B 神某门课的排名为 \(R\),则表示有且仅有 \(R-1\) 位同学这门课的分数大于 B 神的分数,有且仅有 \(N-R\) 位同学这门课的分数小于等于 B 神(不包括他自己)。 我们需要求出全系所有同学每门必修课得分的情况数,使其既能满足 B 神的说法,也能符合 D 神查到的排名...
CF622F The Sum of the k-th Powers 题解
CF622F The Sum of the k-th Powers 题解 题目链接:The Sum of the k-th Powers 题意: 给定 \(n,k\) ,求 \[ f(n,k)=\sum_{i=1}^ni^k \pmod{10^9+7} \] 数据范围:\(1 \le n \le 10 ^ 9, 0 \le k \le 10 ^ 6\)。 考虑 \(k\) 固定时的情况。可以证明,函数 \(f(n) = \sum_{i=1}^ni^k\) 是一个 \(k+1\) 次多项式。 证明 考虑把 \(\sum_{i=1}^n i^k\) 看作 \(n^k+(n-1)^k + \cdots + (n-(n-1))^k\) 暴力展开以后,可以发现这是 \(n\) 个 \(k\) 次多项式,即 \(k+1\) 次多项式。证毕。 由于 \(k\) 比较小,所以考虑随便找 \(k+2\) 个点(取 \(n=1,2\cdots,k+2\) 即可)代入 因为 \(k+2\) 个点 \((x_i,y_i)\) 可以唯一确定 \(k+1\) 次多项式,根据拉格朗日插值法可知 \[ ...
CF1625E2 Cats on the Upgrade (hard version) 题解
CF1625E2 Cats on the Upgrade (hard version) 题解 题目链接:Cats on the Upgrade (hard version) 题意: 本题和 CF1625E1 的唯一区别在于,本题有修改操作。 给定一个长度为 \(n\) 的仅包含 (、) 的字符串 \(s\)。给出如下定义: 定义某字符串是一个简单的合法括号序列,当且仅当我们可以通过若干次移除一个 . 或者一个连续的子串 () 的操作将这个字符串删空,且这个字符串不以 . 作为开头或者结尾。 定义 \(s[l\dots r]\) 为字符串 \(s\) 从第 \(l\) 个字符开始到第 \(r\) 个字符结束的子串。 定义 \(s_x\) 为字符串 \(s\) 的第 \(x\) 个字符。 一共有 \(q\) 次操作,每次操作分为如下两类: 1 l r:将 \(s_l\) 和 \(s_r\) 替换为 . 。保证 \(s[l\dots r]\) 以 ( 开头,以 ) 结尾,且中间所有字符都为 .。 2 l r:询问有多少个 \(s[l\dots r]\) 的子串是简单的 RBS。...
【生物】二分裂与无丝分裂的区别
【生物】二分裂与无丝分裂的区别 二分裂一般为原核生物(如细菌)和单细胞真核生物的分裂方式,细胞遗传物质经过复制后,平均分配给两个子细胞,完成一次分裂形成两个大小相等的子细胞。 无丝分裂又称为直接分裂。在真核细胞分裂的方式中,无丝分裂发现最早,是一种简单而常见的分裂方式。无丝分裂主要出现在高等生物(真核细胞)已分化的细胞中,如蛙的红细胞。 无丝分裂有缢裂、芽裂、碎裂、变形虫状分裂、臂裂等多种方式。尽管不同的真核生物的无丝分裂方式存在着些微差异,但分裂过程基本相似,有的细胞在核仁先伸长横缢为两个或多个,这一点上与二分裂有所不同。随着细胞核的伸长,核仁向核的两端移动,然后在核的中部从一侧或多侧向内凹陷横缢,使核呈肾形或哑铃形,最后分裂为两个或多个子核。与此同时,细胞质也被拉长,并在子核之间发生横缢,继而在光面内质网的参与下形成细胞膜,最终分裂为两个或多个子细胞。整个过程中核膜和核仁都不消失,没有染色体和纺锤体的出现,看不到染色体的规律性变化,故称之为无丝分裂。
快速沃尔什变换 FWT
快速沃尔什变换 FWT 模板题链接:P4717 【模板】快速莫比乌斯/沃尔什变换 (FMT/FWT) 题意: 给定长度为 \(2^n\) 两个序列 \(A,B\),设 \[ C_i=\sum_{(j\operatorname\circ k) = i}A_j \times B_k \] 分别当 \(\operatorname\circ\) 是 or, and, xor 时求出 \(C\)。 输入格式: 第一行,一个整数 \(n\)。 第二行,\(2^n\) 个数 \(A_0, A_1, \ldots, A_{2^n-1}\)。 第三行,\(2^n\) 个数 \(B_0, B_1, \ldots, B_{2^n-1}\)。 输出格式: 三行,每行 \(2^n\) 个数,分别代表 \(\operatorname\circ\) 是 or, and, xor 时 \(C_0, C_1, \ldots, C_{2^n-1}\) 的值\(\bmod 998244353\)。 数据范围: \(1 \le n \le 17\)。 \(\mathcal{Part}\ 0\) 简介 在 OI 中...
CF438E The Child and Binary Tree 题解
CF438E The Child and Binary Tree 题解 题目链接:The Child and Binary Tree 题意: qry 很喜欢计算机科学,而且尤其喜欢二叉树。 考虑一个含有 \(n\) 个互异正整数的序列 \(c_1,c_2\cdots,c_n\)。如果一棵带点权的有根二叉树满足其所有顶点的权值都在集合 \(\{c_1,c_2,\cdots,c_n\}\) 中,qry 就会将其称作神犇的。 并且她认为,一棵带点权的树的权值,是其所有顶点权值的总和。 给出一个整数 \(m\),你能对于任意的 \(1\leq s\leq m\) 计算出权值为 \(s\) 的神犇二叉树的个数吗? 我们只需要知道答案关于 \(998244353\) 取模后的值。 参照下图以更好的理解什么样的两棵二叉树会被视为不同的。 输入格式: 输入第一行有 \(2\) 个整数 \(n,m\) \((1\leq n,m\leq 10^5)\)。 第二行有 \(n\) 个用空格隔开的互异的整数 \(c_1,c_2\cdots,c_n\) \((1\le c_i\le10^5)\)。 输出...

![洛谷P7155 [USACO20DEC] Spaceship P 题解](/qwq/img/p221.webp)
![洛谷P2495 [SDOI2011] 消耗战 题解 & 虚树模板](/qwq/img/p189.webp)
![洛谷P7735 [NOI2021] 轻重边 题解](/qwq/img/p148.webp)
![洛谷P7984 [USACO21DEC] Tickets P 题解](/qwq/img/p55.webp)
![洛谷P3270 [JLOI2016] 成绩比较 题解](/qwq/img/p158.webp)






![洛谷B3869 [GESP202309 四级] 进制转换 题解](/qwq/img/p184.webp)

![洛谷B3883 [信息与未来 2015] 求回文数(加强版) & B3882 题解](/qwq/img/p214.webp)
![洛谷B3879 [信息与未来 2015] 连续数的和(加强版) & B3878 题解](/qwq/img/p230.webp)