祝馀宫

前置知识：矩阵快速幂出门右转 【算法介绍】矩阵乘法 | 祝馀宫 喵！ 例一：斐波那契前缀和直接求斐波那契的例子已经在上面的文章中讲过了。这里直接开始讲斐波那契的前 n 项和怎么算。 求斐波那契的前 $n$ 项和对于 $m$ 取模的结果。 首先，不难给出递推式： \begin{cases} f_1 = 1\\ f_2 = 2\\ f_i = f_{i - 1} + f_{i - 2} \quad (i\ge 3)\\ s_1 = 1\\ s_i = s_{i-1} + f_i\qquad (i\ge 2) \end{cases}这个是最最基础的递推式子，我们不难想到之前说的列方程法。我们就可以写出下面的方程组。 \begin{cases} f_{i+1} &= &0\times f_i + 1\times f_{i+1} + 0\times s_i \\ f_{i+2} &= &1\times f_i + 1\times f_{i + 1} + 0\times s_i \\ s_{i+1} &= &0\times f_i + 1\times f_{i + 1} + 1\times ...

上午：CSP-J 2024题目钛简单，没有打到 300 分的原因是 T3 没有算内存，直接把打表用的程序交了上去喜提 MLE -50 下午：CSP-S 2024题目还是好简单，没有打到 220 分的原因是： T1 先把被吃的赋值成了 0，然后再让吃的把被吃的吃了…… -25 赛后扫了一眼代码就改了出来，最煞笔的是大样例全过了…… T2 把已经平方的速度再次平方…… -60，也是赛后看了一眼代码就发现了问题，最傻逼的是赛时我调这个问题调了一整个比赛…… 导致 T3 的暴力分都没打…… T3 ，T2 的策略规划不周，以及最傻逼的考场发挥，暴力分没打…… -20 这次 S组 比赛总计挂分 105 分，直接把大众分打成了煞笔分，我是纸张

题面题面翻译有 $n$ 个点，$m$ 条边的图，每条边有一种颜色。定义一条路（经过的点是 $c_1,c_2,\dots,c_k$）是彩虹路，要求满足 $2$ 个条件： 对于所有 $1 \le i \le k - 1$，$c_i$ 和 $c_{i+1}$ 有边。 对于所有 $1 \le i \le \dfrac{k-1}{2}$，$c_{2i}$ 和 $c_{2i-1}$ 的边的颜色与 $c_{2i}$ 和 $c_{2i+1}$ 的边的颜色相同。 现在有 $q$ 次操作： x y z：向点 $x$ 和 $y$ 之间建一条颜色为 $z$ 的边。 ? x y：询问 $x$ 点和 $y$ 点之间是否有彩虹路。 思路我们首先可以想到 对于点 xx，它连出去的同种颜色连着的点都是可以相互到达的，所以我们可以将它们用并查集合并。我们要快速查询一个点连出去某种颜色的边，这里用了一个 map 。这样我们就处理完了走偶数步的情况，对于走奇数步的情况，最后一步是随便走的，我们可以对每个集合存一个 set，存集合中能一步走到的点，启发式合并即可 代码1234567891011121314151 ...

题面原题链接大秦 为你打开 题目传送门 题目翻译给定一个以 $1$ 为根的 $n$ 个结点的树，每个点上有一个字母（a-z），每个点的深度定义为该节点到 $1$ 号结点路径上的点数。每次询问 $a, b$ 查询以 $a$ 为根的子树内深度为 $b$ 的结点上的字母重新排列之后是否能构成回文串。 思路首先这道题目一眼就是树上启发式合并，我们大力统计每一个点以及他们的子树里面每个深度每种字母有多少就可以了。代码并没有什么细节敲板子即可。 代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129 ...

题面原题链接大秦 为你打开 题目传送门 题目翻译你有一棵无根树，点数为 $n$，每个点有个点权 $a_u$，定义一条路径 $P(u,v)$ 的权值为经过的所有点的点权的异或和。定义一棵树是合法的，当且仅当树上所有简单路径（只经过每个点一次的路径）的的权值都不为 $0$。 你可以对权值进行修改，可以改成任意正整数，问最少修改多少次才能让这棵树合法。 输出最小修改次数。 $n\leq 2\times 10^5,a_i\leq 2^{30}$ 思路我们不难发现，如果一条路径上的元素异或值为 0 我们设 $dep_i$ 表示 $i$ 号点到根所有路径的值。 那么这个路径一定满足条件 $dep_u\ \oplus\ dep_v\ \oplus\ dep_{lca(u,v)} = 0$ 。那么我们就不难想到，处理出这个节点所有儿子的左右子树里的 dep 值。如果 $v$ 的子树之中存在一个值等于 $u$ 的子树中的一个节点的值异或当前这个节点的值，那么一定存在一条路径在这两个子树之中。那么一劳永逸的方式就是把当前这个作为 lca 的节点替换了，统计答案。 代码1234567891011121314 ...

题面题目链接大秦 为你打开 题目传送门 备用题面给定若干未赋值的变量，并给出 $n$ 组操作，每组操作形如：x y p 。当 $p$ 为 $1$ 时，如果第 $x$ 变量和第 $y$ 个变量可以相等，则输出 YES ，并限制他们必须相等；否则输出 NO ，并忽略此次操作。当 $p$ 为 $0$ 时，如果第 $x$ 变量和第 $y$ 个变量可以不相等，则输出 YES ，并限制他们必须不相等；否则输出 NO ，并忽略此次操作。 思路显而易见的相等关系肯定是用并查集存储，而不等关系我们只需要用 vector 存下来有以后大力合并即可。 代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103// #pragma GCC optimize(2)// ...

题面：[HNOI2009] 梦幻布丁题目描述$n$ 个布丁摆成一行，进行 $m$ 次操作。每次将某个颜色的布丁全部变成另一种颜色的，然后再询问当前一共有多少段颜色。 例如，颜色分别为 $1,2,2,1$ 的四个布丁一共有 $3$ 段颜色. 输入格式第一行是两个整数，分别表示布丁个数 $n$ 和操作次数 $m$。第二行有 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个布丁的颜色 $a_i$。接下来 $m$ 行，每行描述一次操作。每行首先有一个整数 $op$ 表示操作类型： 若 $op = 1$，则后有两个整数 $x, y$，表示将颜色 $x$ 的布丁全部变成颜色 $y$。 若 $op = 2$，则表示一次询问。 输出格式对于每次询问，输出一行一个整数表示答案。 样例 #1样例输入 #1123454 31 2 2 121 2 12 样例输出 #11231 提示样例 1 解释初始时布丁颜色依次为 $1, 2, 2, 1$，三段颜色分别为 $[1, 1], [2, 3], [4, 4]$。一次操作后，布丁的颜色变为 $1, 1, 1, 1$，只有 $[1, 4]$ 一段颜色。 数据规 ...