序列自动机
浅谈序列自动机 link 序列自动机是淦什么的 序列自动机好高级的名字用于解决子序列问题，可以在线性时间判断串 TTT 是否是串 SSS 的子序列，这篇文章主要介绍两种方法实现。 做法 1 我们求出一个数组 fi,cf_{i,c}fi,c 表示在模式串 SSS 中位置 iii 后字符 ccc 第一次出现的位置。这个很简单，我们倒序枚举 SSS，从 i+1i + 1i+1 继承值并更新。 f
三元环计数问题
三元环计数问题 link，给定一个无向图，求其中三元环的数量。 1≤n≤1051 \le n \le 10^51≤n≤105，1≤m≤2×1051 \le m \le 2 \times 10^51≤m≤2×105 。 构造一个这样的有向图：对于原来图中的每一条无向边，改为由度数小的向度数大的连边，若相等则由编号小的向编号大的连边，在这样的图中，三元环 {x,y,z}\{ x,y,z\}{x,
P3306 题解
P3306 题解 link，给出 ppp，aaa，bbb，x1x_1x1，求第一个 xi=tx_i = txi=t。 xi+1≡a×xi+b(modp)x_{i + 1} \equiv a \times x_i + b \pmod{p}xi+1≡a×xi+b(modp) 。 0≤a,b,x1,t<p0 \le a, b, x1, t < p0≤a,b,x1,t<p，
BSGS（大步小步）算法学习笔记
BSGS（大步小步）算法学习笔记 前置芝士 会取模运算就行啦！ 正文部分 拔山盖世 BSGS\tt{BSGS}BSGS 算法用于求解 ax≡b(modp), a⊥pa^x \equiv b \pmod{p}, \ a \perp pax≡b(modp), a⊥p 中 xxx 的值。 设 x=ti−jx = ti - jx=ti−j，t=⌈p⌉t = \left \lceil \sqrt{p}
exgcd（扩展欧几里得）学习笔记
exgcd（扩展欧几里得）学习笔记 前置芝士 基础的模、整数运算； gcd\gcdgcd 的求法，即 gcd(a,b)=gcd(b,a mod b)\gcd(a, b) = \gcd(b,a \bmod b)gcd(a,b)=gcd(b,amodb)； 裴蜀定理，二元一次方程方程 ax+by=cax+by=cax+by=c 有解的充要条件是 gcd(a,b)∣c\gcd(a, b)
网络流 24 题 部分水题题解
网络流 24 题 部分题题解 注：代码只给出主程序部分，网络流板子基本相同。 方格取数问题 link 给定 mmm 行 nnn 列的网格，每个格中有数，你可以取任意个格子的数，但不能同时取相邻的格子（四联通），求取出数的和的最大值。 1≤n,m≤1001 \le n,m \le 1001≤n,m≤100，1≤ai,j≤1051 \le a_{i, j} \le 10^51≤ai,j≤105
网络流学习笔记
网络流学习笔记 注：笔者比较菜，许多证明没有给出，一些地方可能有误。 一些定义 网络 对于一张有向图 G∈(V,E)G \in (V, E)G∈(V,E)，有一个源点 S∈VS \in VS∈V 和一个汇点 T∈VT \in VT∈V，每一条边 (u,v)∈E(u, v) \in E(u,v)∈E 有一个限流 c(u,v)c(u, v)c(u,v)。特别的，∀(u,v)∉E , c(u
CF1383D 题解
CF1383D 题解 题意 给定一个长度为 nnn 的序列 aaa，选出 aaa 中的若干个元素使得和为零。 数据范围 ：1≤n≤1061 \le n \le 10^61≤n≤106，i−n≤ai≤1−ii - n \le a_i \le 1 - ii−n≤ai≤1−i 题解 构造题，i−n≤ai≤1−ii - n \le a_i \le 1 - ii−n≤ai≤1−i，即 1≤i−ai