CF1553I Stairs 说实话网上的题解真的少，这个算是当前最详细的吧。请原谅我参考了别人的代码，还跑得巨慢的这一事。 不过还是 $O(n^2)$ 过去了，嘻嘻。 有两个思路，是将贡献不同时间计算的结果。 首先一个合法的序列，肯定是将数值连续的一段拿出来，然后可以分成若干段等长的。这个一开始判断一下即可。 之后我们将分段拿出来不妨将其记录为 $s$ 数组。 一个合法的序列就是不能有任意两个 $s$ 构成单调序列。 但是这个需要复杂度较高的 $dp$，我们考虑通过容斥改成钦定有几个数不合法。 对于一个长度 $> 1$ 的段，其有两种单调性。长度为 $1$ 的段，其只有一种单调性，但是向后转移的时候会产生两种单调性。 $\tt Case\ 1$ 我们将单调性在这个序列转移的时候就计算贡献。 设 $f(i, j, 0/1)$ 表示当前考虑到第 $i$ 个序列，已经钦定了 $j$ 个连续，当前段长度是否是 $1$。注意这个段是表示已经拼接之后的段。$$\begin{aligned}& f(i - 1, j, 0) \to f(i, j + 1, 1) \& f( ...

CF375D Tree and Queries线段树合并。 需要记录两颗线段树，其中一棵表示当前节点的颜色数量，另外一个表示出现次数为 $i$ 的颜色个数。 前面一棵直接进行线段树合并即可。后面的那棵能线段树合并的条件当且仅当有一种颜色只在一个子树中出现，我们可以直接对于这种情况进行合并。不然我们需要修改颜色，也就是暴力修改。 暴力修改的次数最多是 $O(n)$ 次。复杂度正确。 $Tricks：$ 我们先将可以进行合并的节点进行合并，之后再暴力修改。具体来说就是先统计哪个颜色是不符合标准的，之后将包含这个颜色的节点的所有贡献减去。之后直接线段树合并即可。 我们可以在线段树合并到叶子节点的时候记录同一个颜色在几个子树中出现过。 注意： 在线段树合并结束的时候不要忘记将权值合并。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828 ...

$\tt luogu\ P2664 \ 树上游戏$题目大意： 一棵树上每个节点都有颜色，给定一个长度为 $n$ 的颜色序列，定义 $s(i, j)$ 为 $i \to j$ 的颜色数量。 设 $sum_i = \sum_{j = 1} ^ n s(i, j)$。求所有的 $sum_i$。 这个本质可以看成树上的点对的问题。既然不考虑在线我们可以使用离线算法点分治。 我们需要在 $O(n)$ 或者 $O(n \log n)$ 的复杂度完成统计以当前节点为 $lca$ 的点对的所有贡献。 显然暴力统计是不行的。考虑借鉴一下统计树上距离为 $k$ 的点对的方法，开桶进行计算。 首先考虑以根节点为起点的方案数，也就是考虑每一条链上第一个出现的节点，其对于根的贡献是其子树大小。 其子树中每一个点都会产生一次这样颜色的贡献。 为了方便统计我们将根节点的颜色也加上贡献，同时提前打上标记。 之后需要统计点对的贡献。我们不妨将上一次产生贡献的点的贡献记成 $f(i)​$。那么不产生贡献显然是 $f(i) = 0​$。 既然是统计子树中的贡献。考虑遍历每一个子树。 对于每个点的贡献就是。设当前的颜色 ...

CF587F Duff is Mad暴力就是每个串都在自动机上跑一下。 稍微优化一下就是之前跑过的就不跑了。 在跑的时候把所有的答案都记录下来。 之后考虑进行根号分治。 如果说当前串的长度 $> \sqrt n$ 那么出现次数肯定 $< \sqrt n$。我们直接进行暴力跑，是可以接受的。 对于长度 $< \sqrt n$ 的串，我们考虑建立 $fail$ 树。之后从根节点开始遍历，对于每一个结束标记都放到主席树里面去。 对于查询的时候从上到下走自动机上的节点加上对应的贡献即可。 使用主席树维护每一个节点的前缀和即可。 省空间。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109 ...

CF738 div2 VP主要是 $\tt Alkaid$ 这个老哥要打。然后早上我在写题，写完了发现他还在搞 $C$。那就顺便打一下。 感觉上我的水平 $E$ 是做不出来的。 因为我一直在想质因数分解 $\dots$ $\tt A$睿智题目，题目上说操作次数是无限的，所以最终答案每个数都能被 $&$ 一次。因为 $&$ 后的值不会变大，最终答案就是每个数 $&$。 $\tt B$因为我比较懒直接一个 $dp$ 就搞完了。 设 $f(i, 0/1)$ 表示考虑到当前位，当前填 $R/B$ 的最小花费。 $\tt C$最终答案肯定一一条链再到 $n + 1$ 再回来继续链。注意特判可以从 $n + 1$ 当做起点的情况。 $\tt D1$猜测一下最终图肯定有一个是树。 如果说不是树，那么有两个联通块 $A, B$ 在一个图上不联通，在另一个图上联通。设其为 $C$。如果 $C, D$ 不联通，在另一个图上肯定 $C, D$ 联通。通过归纳法可以得到肯定有个图是树。 既然最终是树那么暴力枚举即可。 $\tt D2$都说了是树，那么我们考虑对于集合的连边情况，如果 ...

ABC212G Power Pair给你一个质数 $P$。求点对 $(x, y), x, y \in [0, P - 1]$ 的点对数量。 其中 $x^k \equiv y \pmod P$。 可以想到如果能把指数拿下来会就变成一个乘积的形式，那么能将指数取下来的情况也就是底数相同。题目中给定的是一个素数 $P$。这也就是意味着其缩系的大小就是 $P - 1$。然后质数的原根也就是 $P - 1$。能表示题目中的任意数。 那么我们可以转换到 $g^{ka} \equiv g^b \pmod P$ 我们就可以把指数取下来。得到 $ka \equiv b \pmod {P - 1}$。我们把形式转换一下得到 $ka - y(P - 1) = b$。 根据 $\tt Lucas$ 定理这个方程有解的条件就是 $b | \gcd(a, P - 1)$。 这边可以将 $k$ 当成 $x$ 会更加显然。 那么 $b$ 的数量就是 $\frac{P - 1}{\gcd(a, P - 1)}$。 做法 $1$： 那么可以得到柿子 $\sum_{i = 1} ^ {P - 1} \frac{P -1 ...

Topcoder SRM 641 BitToggler题目大意： 给定一个长度为 $n$ 的 $01$ 序列，给定当前位置，每一次会等概率随机走到一个除了当前点的任意位置，并且取反走到的当前点，其花费两个点的距离。求期望多少花费能让整个序列的所有数相同。 因为期望具有线性，所以我们考虑对于全部的操作都是由若干条 $(u, v)$ 边构成的，所以我们对于一条边考虑在最终答案上被计算了几次。 但是发现对于一条边的两个点 $(u, v)$ 我们还需要保存其他点的信息。 其实不然，容易想到找到当前有多少个点是 $1$ 即可。 其次我们还需要知道 $a_u, a_v$ 所以我们可以设置状态。 $f(a, 0/1, 0/1)$ 表示剩下 $n - 2$ 个点中有多少个点是 $1$。点 $i, j$ 的颜色信息。这个表示 $i \to j$ 这条边在整个序列到达结束状态的时候使用了几次。 我们考虑什么时候会产生 $1$ 的路径贡献，也就是一开始 $i$ 是起点的时候，这是一开始的初值。 然后我们考虑转移： 从 $!a_j$ 转移过来，这个时候 $j$ 需要是起点。 从 $!a_i$ 转移过来。 从 ...

P7418 [USACO21FEB] Counting Graphs P题目大意： 给定一张图，对于另一张合法的图，当且仅当两张图 $(u, v)$ 之间所有的路径长度相同。统计所有合法的图的数量。注意路径不一定是简单路径。 看到路径不一定是简单路径基本上就可以猜到做法了。因为是复杂路径一条边重复走是增加 $2$ 的贡献，所以只要任意两点之间最短奇偶路径相同即可。我们可以找出这样的路径。我们任意找一个起点，之后可以得到 $n$ 个数对。我们为了方便钦定 $(x, y), x < y$。 我们考虑一条边可以产生贡献而且是合法的是什么情况。对于一个 $(x, y)$ 来说之前的点对 $ + 1$ 必须保证 $x_1 +1 - x\equiv 0\pmod 2, y$ 同理。然后我们不一定每一个点都要考虑，直接继承就好了。 所以总共有 $3$ 种点。 (x - 1, y - 1)是 $A$ 类边，点个数为 $a$。 (x - 1, y + 1)是 $B$ 类边，点个数为 $b$。 (x + 1, y - 1)是 $C$ 类边，点个数为 $c$。 (x, y)是当前的点对，点个数为 $ ...