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} ...

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_ ...

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)是当前的点对，点个数为 $ ...

CF1534F2发现这是一个 $4$ 联通问题。我们先考虑建图。 我们需要每一个序列都满足条件，那么我们可以选取最低的点然后考虑其被左右两边影响的区间，也就是左右两边任意掉落一个沙子即可将其掉落。 这个可以使用 $dfs$ 解决。然后我们就得到 $n$ 个满足条件的区间。 我们将题目变成了给定 $n$ 个区间，选择最少的点使得每一个区间至少有一个点。我们按照左端点为第一关键字，右端点为第二关键字排序。尽量选右边的点即可。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119#include <bits/stdc++.h>using na ...

CF1305G 可以算说我自己做出来的 $3500$ 题吧。虽然这是很多年前的题。 这个东西我们可以尝试一下建图，也就是如果两个点是朋友关系我们可以使其连边。 然后会发现有很多的联通块，那么我们不妨对于一个联通块来考虑。 我们贪心得想肯定要让小的邀请大的点。然后邀请的情况肯定构成一个树，也就是邀请的边数是点数 $-1$。 因为不能重复邀请。 我们考虑这个树的情况需要使用，会想到最大生成树。然后要如何设置边权？可以发现对于一条边本质上两边都可以使用那么边权就是 $a_u + a_v$。但是每一个点肯定需要一次被加入，那么就需要减去所有点的点权。 但是我们第一个选择的点不知道是谁，总不可能暴力枚举吧，发现可以建立一个 $0$ 节点，链接所有的节点，这样第一个点的贡献也可以计算了。 现在可以保证整张图是联通的，我们计算最小生成树即可。 最小生成树总共有 $3$ 种求法。$prim$ 和 $kruscal$ 都需要预先知道全部的边。那么我们可以使用 $Boruvka$。在计算的过程中我们只需要进行高维前缀和即可。 因为最大的边权可能被计算过了，那么我们维护一个和最大边权所属联通块不同的次 ...

CF980F每一个点都指属于一个环，考虑对于每一个环进行计算答案。 考虑基环树的情况，我们会计算出其余的点，之后对于环上的点单独进行 $Dp$。 这边也是同理，找到每一个点属于的环，钦定一下每一个环的根。 因为计算距离需要使用换根 $Dp$。 我们考虑需要预处理写什么，也就是对于不同环之间的转移，然后对于同一个环内我们需要记录环根的答案。 对于不同环之间的转移，对于每一个点设 $f0_i$ 表示向下，从所属环不同的点到当前环的最小距离。 然后对于环根还要特别记录一下 $f1_i$ 表示考虑环上的情况。 因为环根才可以将之前的节点都考虑到。 之后设 $f_i = \max(f0_i, f1_i)$ 也就是向下走的答案。 之后考虑向上走，设 $g_i$ 表示向上走的答案。 我们这个时候可以将 $f0_i = \max(f0_i, g_i)$ 方便处理。 可以从所属环不同的点进行转移，记录最大最次大值。 之后考虑整个环对于当前点进行转移，也就是 $\min(l, r)$ 左右两边，我们分别对其进行单调队列即可。 可能因为我代码实现问题，我的数组需要多开大几倍。 12 ...