Colythme

好了，又是爆零的一天，恭喜我自己 $\text{score：0 + 0 + 0 = 0 rk：27/27}$ Problem A：小卖部题目描述ysgh 是一名数数大师。 现在小卖部有 $n$ 种商品，第 $i$ 种有 $a_i$ 个，价格为 $b_i$。 ysgh 总共去了 $Q$ 天小卖部，第 $i$ 天他只会购买编号在 $l_i \sim r_i$ 的商品。他的卡里有 $c_i$ 元，因此他只能购买价值和不超过 $c_i$ 元的物品。 ysgh 想要知道有多少种购买物品的方案。由于答案很大，你只需要输出答案对 $1000000007$ 取模后的结果。两种方案被认为是不同的当且仅当存在一种物品，其购买数量不同。 当然，ysgh玩了个小花招，你需要通过上一个询问的答案来推导下一个询问的参数。 数据范围对于所有测试数据，满足 $1 \le n \le 10000, ~ 1 \le Q \le 50000, ~ 1 \le a_i, b_i, c_i \le 1000, 1 \le l’_i, r’_i \le n$ 题解令 $C = 1000$ 首先看得出来可以用生成函数搞，显然答 ...

晚了几天写，暴力场 $\text{score：40 + 40 + 45 = 125 rk：17/30}$ Problem A：Tree题目描述 数据范围对 $100\%$ 的数据，$1 \le n \le 10^8, ~ 1000 \le k \le 10^8$ 题解很容易发现，满足条件等价于要求树中没有任意一条从根出发的路径经过超过 $k - 1$ 个左儿子 然后就是一个很妙的转换，将树按如下规则变为括号序列： 子树 $u$ 括号序 = ‘(‘ + ‘$u$ 左子树括号序’ + ‘)’ + ‘$u$ 右子树括号序 给个题解的图例 实际上可以不用考虑叶节点，那么现在将 $n$ 变为 $n - 1$，$k$ 变为 $k - 2$ 那么现在的任务就变为在坐标系中将左括号看作往右上角走，右括号看作往右下角走，从 $(0, 0)$ 最终走到 $(2n, 0)$ 的方案数，并需要满足过程中纵坐标始终在 $[0, k]$ 中的方案数（注意此时 $n, k$ 已变化） 这就是类似卡特兰数，但是有两条限制，即不能碰到 $y = - 1$ 也不能碰到 $y = k + 1$ 又从 $(x1, y1 ...

中下 $\text{score：24 + 40 + 0 = 64 rk：23/34}$ Problem A：Mythological V题目描述小S打算送给小M一棵 $n$ 个点的圣诞树，点从 $1$ 到 $n$ 标号，他打算给树上挂上 $m$ 个礼物，每个礼物在树上的某个点上，礼物可以重叠。 小M给了小S $q$ 个限制，其中第 $i$ 个形如“第 $a_i$ 个礼物和第 $b_i$ 个礼物在树上的最短路径经过了点 $c_i$”。 小S想要构造出符合小M条件的挂礼物方案。可怜的小S当然不会啦，所以他向你求助。 数据范围对 $100\%$ 的数据，$n, m \le 250, ~ q \le 5 \times 10^4$ 题解好久没写过 $2-SAT$ 了 虽然我的暴力虽然 $\text{WA}$ 了但竟然没有 $\text{T}$？说不定改对了能过呢 考虑两个礼物 $a, b$ 放置位置经过 $c$ 代表着什么，说明 $a, b$ 放置的位置在以 $c$ 为根的树上位于不同的 $c$ 儿子的子树上 那么现在以 $1$ 为根，设 $g_{i, j, 0}$ 表示第 $j$ 个礼 ...

没交 $\text{score：NULL rk：NULL}$ Problem A：区间第k小题面 题解先考虑离线，整体二分，二分答案 $mid$，处理所有 $\le mid$ 的数，那么此时问题就转化为在区间出现次数不超过 $w$ 的数有多少个 不妨关注每个数对询问区间 $[L, R]$ 的贡献，对某个数 $a$，若它是从左往右后 $w$ 个出现为 $a$ 的数，则它的贡献为 $1$，若为倒数第 $w + 1$ 个则贡献为 $- w$，剩下的贡献都为 $0$，那么我们就可以开一个队列，首先总大小（即不删去超过 $w$ 的）算出来，此时计算需要删去的，队列大小未到 $w$ 时没有需要删的，若大于 $w$ 时每次就让队首点贡献减去 $w + 1$，当然之前多减的还要加回来 那么现在就可以考虑从离线转成在线，在整体二分的过程中每一层（即每一次二分的 $[l, r]$）都会建一些可持久化线段树，而它又最多会修改 $O (n \log n)$ 次，开 $O (n \log^2 n)$ 个节点，所以把每一层的可持久化线段树都存下来，在线二分时即可直接查找，总时间复杂度 $O ...

线段树求直径可以求任意子树（包括连子树都不算的分散节点集合）的直径，适用范围广。 线段树的每个节点所对应的区间$[L, R]$，指代了$Dfn$在$[L, R]$内节点，其中线段树上每个节点存储了$diam$（当前区间直径）及$lp, rp$（当前直径对应的左右端点），每次$Merge$操作分为全左区间、全右区间和横跨两个区间作讨论，对于第三种情况，选择两侧原直径端点求$Dist$取最值即可，正确性显然，查询直接通过$Dfn$查询即可。 当然可能有一些区间内的点不连通，先当作它们连通即可。 对于删除某些子树，相当于把整棵树分为$n$部分，查询每个部分，全部$Merge$起来即可。 例题Snow的追寻 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101 ...

给定一个 $n$ 个点的竞赛图，给该图的每条边染色，颜色数量不能超过 $m$ 个，一个染色合法当且仅当不存在长度为 $2$ 的路径，即对有向图中任意路径 $i \rightarrow j \rightarrow k$ 均有边 $i \rightarrow j$ 和边 $j \rightarrow k$ 颜色不同 $2 \le n \le 3000, ~ 2 \le m \le 26$ 设该竞赛图点集 $V$ 考虑染每一种颜色意味着什么，相当于选择一个点集 $S \subseteq V$，将所有边 $(u, v)$ 满足 $u \in S \cap v \in \complement_VS$ 染上该颜色，也就是说我们要找到至多 $m$ 个这样的集合来覆盖所有的边 这样可以给出一个 $m = 2\log n$ 的染色方案，对所有点分治，每次一分为二，给 $S, \complement_V S$ 之间的边按两种方向染上不同的颜色，这样总共需要颜色是 $2\log n$ 的 但实际上可以用二进制来表示这种是否在每个 $S$ 中的关系，对每个 $S_i$，若当前点 $u$ 得到的二进制位 ...

该文为（金策《生成函数的运算与组合计数问题》）学习笔记 幂级数级数：一个有穷或无穷序列 $a_0, a_1, a_2, …$ 的形式和「即 $\sum\limits_{i = 0} a_i$」被称为级数，序列中的项称作级数的通项 敛散性：极限是无穷即为发散「如 $f(x) = x$」；极限不为无穷即为收敛「如 $f(x) = \frac{1}{x}$」 那么幂级数即为形如 $\sum\limits_{n = 0}^{\infty} a_n(x - c)^n$ 或者化简为 $\sum\limits_{n = 0}^{\infty} a_nx^n$ 的形式 形式幂级数形式幂级数$$A(x) = \sum\limits_{n = 0}^{\infty} a_nx^n$$形式与幂级数很像，但这里 $x$ 作为一个符号而不用具体数值带进去算，也不研究敛散性什么的 形式幂级数的加减乘法与多项式的有着类似的定义 实际运算时一般在 $\bmod{x^n}$ 的意义下进行，即仅取次数不超过 $n - 1$ 的项 笛卡儿积「直积」有集合 $A, B$，则 $A, B$ 的笛卡儿积记作 $A \times ...

概念引入数论函数　　　　指定义域为正整数的函数　　　　定义其加法为逐项相加，即$(f + g)(n) = f(n) + g(n)$　　　　定义其数乘为逐项相乘，即$(xf)(n) = x × f(n)$ 单位元　　　　单位元是集合中一种特别的元素，当单位元与其它元素相结合时，不会改变其它元素的值 逆元　　　　逆元是指可以取消另一给定元素运算的元素，即将其变回单位元 符号表示　　　　$[A]$表示条件$A$是否为真　　　　此处的符号”$*$”表示狄利克雷卷积 狄利克雷卷积　　令$t(n) = f(n) * g(n)$，则 　　 $$t(n) = \sum\limits_{i | n} f(i)g(\frac{n}{i})$$ 　　那么狄利克雷卷积显然有下面几个性质： 满足乘法交换律、结合律、分配律 对于单位元$\epsilon(n) = [n = 1]$，满足$\epsilon(n)*f(n) = f(n)$　　　　- 对于每一个$f(1) \ne 1$的数论函数$f(n)$，皆存在其逆元$f^{- 1}(n)$，满足$f(n) * f^{- 1}(n) = \epsilon(n)$，那 ...

根据Crash的数字表格，很容易可以将式子化简为$$\begin{aligned} Ans &= \sum\limits_{i = 1}^n \sum\limits_{j = 1} ij(i, j) \\ &= \sum\limits_{d = 1}^n d^3 \sum\limits_{k = 1}^{\left\lfloor\frac{n}{d}\right\rfloor} \mu(k) k^2 \left( \sum\limits_{i = 1}^{\left\lfloor\frac{n}{kd}\right\rfloor} i \right)^2 \end{aligned}$$感觉 $d, k$ 放在一起式子无法继续化简，主要是有 $kd$ 存在，故令 $T = kd$ ，则有$$Ans = \sum\limits_{T = 1}^n \left( \sum\limits_{i = 1}^{\left\lfloor\frac{n}{T}\right\rfloor} i \right)^2 T^2 \sum\limits_{d | T} d \mu(\frac{T ...

说实话这题写树剖 $LCT$ 什么的真的思想又不难又好实现的样子，但是我还是选择自虐选择了动态点分治 那就两种做法都稍微提一下： 树链剖分 / $LCT$很容易可以发现一个换根操作只会对当前根在原树（根为 $1$ ）上的祖先一条链造成影响，也就是将它们的子树变成除当前链方向其它与之相连的点集，那么用树剖跳，用线段树维护一下原树上从上面来的和从下面来的，再将所有涉及的节点合并，并且删去算重复的和不该算的即可（虽然我没实现但是这个思路应该是对的 动态点分治首先有两篇博客：zzq、租酥雨 因为我们要算 $\sum\limits_{i = 1}^n s_i^2$ ，可以先想一下 $\sum\limits_{i = 1}^n s_i$ 怎么算，因为每个点的贡献只会被祖先计算到，那么易知 $\sum\limits_{i = 1}^n s_i = \sum\limits_{i = 1}^n value_i * (depth_i + 1)$ ，这个直接用动态点分治维护三个变量 $sumo_i, sumt_i, sumfa_i$ （sumo -> $p$ 子节点权值之和, $sumt$ -> ...