Pollard-Rho


问题

[HNOI2014]道路堵塞


题目描述题目传送门思路首先有一个结论:删除边后的最短路一定是在最短路上跑一段,然后跳出最短路,然后再跑一段。换言之,就是不在最短路上跑的路径一定是一段连续的路径,不会存在两段及以上(如果两段相等,假设选择原最短路上的路径)。证明:这个结论是我猜出来的,现在给出简要证明。记 dis⁡(i)\opera

同余


费马小定理 欧拉定理 扩展欧拉定理

选举预测


题目描述题目传送门思路看到 $n \le 10^6$,显然会有一些结论。结论1能打败人最多的人可能胜利。证明:假设打败人最多的人(称其为 Cms)不可能胜利,那必定有人(下文称其为石老板)可以打败他和他所有能打败的人,否则可能出现 Cms 打败的人干掉了石老板,然后 Cms 干掉了他,取得胜利。为了

【模板】扩展 KMP(Z 函数)


题目传送门思路对于一个字符串 $s$,$z_i := |\operatorname{LCP}(s,s[i:])|$,即 $s$ 从 $i$ 开始的后缀与 $s$ 的最大匹配。暴力计算 $z$ 函数是 $O(n^2)$ 的,考虑将计算的 $z$ 函数用起来。我们顺次计算 $z$ 函数,假设现在需要计

[POI2015] LAS


题目描述题目传送门思路这题黑是恶意评分吧考虑 dp,先想状态怎么设。很容易想到的第一种 dp,假设 $dp_{i,j}$($j \in \{1,2\}$),表示第 $i$ 个人吃了左边($j = 1$)或者 右边($j = 2$)的食物,可是这样似乎没有什么转移关系,所以做不了(~~或者我太菜了不会

复数


虚数我们定义 $i = \sqrt{-1}$ ,称 $i$ 为虚数单位。

CF797E Array Queries


题目描述题目传送门1题目传送门2给定长度为 $n$ 的序列 $a$。$m$ 次询问。每次询问给出 $p,k$。您要不断地执行操作 $p\gets p+a_p+k$,直到 $p>n$ 为止。询问的答案为操作次数。$1\le n,q\le 10^5$,$1\le a_i\le n$。思路Algor

[国家集训队]排队


题目描述题目传送门思路对于交换 $i , j$ 的数字,我们考虑交换这两个数字(记这两个数字分别为 $a,b$)对答案的贡献。显然,对于区间 $[i+1,j-1]$ 中每一个大于 $a$ 的数字会产生 $+1$ 的贡献,每一个小于 $a$ 的数字会产生 $-1$ 的贡献,每一个小于 $b$ 的数字会

分块


简介其实,分块是一种思想,而不是一种数据结构。从 NOIP 到 NOI 到 IOI,各种难度的分块思想都有出现。分块的基本思想是,通过对原数据的适当划分,并在划分后的每一个块上预处理部分信息,从而较一般的暴力算法取得更优的时间复杂度。分块的时间复杂度主要取决于分块的块长,一般可以通过均值不等式求出某