前缀树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Node:
    __slots__ = ('children', 'end')

    def __init__(self):
        self.children = defaultdict(Node)
        self.end = False

class Trie:
    def __init__(self):
        self.root = Node()

    def put(self, s):
        curr = self.root
        for i in s:
            curr = curr.children[i]
        curr.end = True

    def find(self, s):
        curr = self.root
        for i in s:
            if i in curr.children:
                curr = curr.children[i]
            else:
                return False
        return curr.end

数位DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
low = "0000"
high = "6789"
n = len(high)

@cache
def DFS(i, lo_limit, hi_limit):
    nonlocal low, high, n
    if i == n:
        return 1

    lo = int(low[i]) if lo_limit else 0
    hi = int(high[i]) if hi_limit else 9
    ans = 0
    for x in range(lo, hi + 1):
        ans += DFS(i + 1, lo_limit and x == lo, hi_limit and x == hi)
    return ans

ans = DFS(0, True, True)

树状数组

video

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class BIT:
    def __init__(self, init):
        if type(init) == list:
            n = len(init)
            tree = [0] * (n + 1)
            for i, x in enumerate(init, 1):
                tree[i] += x
                nxt = i + (i & -i)
                if nxt <= n:
                    tree[nxt] += tree[i]
            self.nums = init
        else:
            tree = [0] * (init + 1)
            self.nums = [0] * init
        self.tree = tree

    def update(self, index: int, val: int) -> None:
        delta = val - self.nums[index]
        self.nums[index] = val
        i = index + 1
        while i < len(self.tree):
            self.tree[i] += delta
            i += i & -i

    def update2(self, index: int, delta: int) -> None:
        self.nums[index] += delta
        i = index + 1
        while i < len(self.tree):
            self.tree[i] += delta
            i += i & -i

    def prefixSum(self, i: int) -> int:
        s = 0
        while i:
            s += self.tree[i]
            i &= i - 1
        return s

    def sumRange(self, left: int, right: int) -> int:
        """[L, R]"""
        return self.prefixSum(right + 1) - self.prefixSum(left)

Dijkstra

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def Dijkstra2(g, x):
    vis = [inf] * n
    vis[x] = 0
    h = [(0, x)]
    while h:
        w, node = heappop(h)
        if w > vis[node]:
            continue
        for i, wei in g[node]:
            nw = vis[node] + wei
            if nw < vis[i]:
                vis[i] = nw
                heappush(h, (nw, i))
    return vis

Z函数

匹配前缀和后缀的公共前缀

1
2
3
4
5
6
7
8
9
10
11
def Z(word):
    n = len(word)
    z = [0] * n
    l, r = 0, 0
    for i in range(1, n):
        if i <= r:
            z[i] = min(z[i - l], r - i + 1)
        while i + z[i] < n and word[z[i]] == word[i + z[i]]:
            l, r = i, i + z[i]
            z[i] += 1
    return z

DSU

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class DSU:
    def __init__(self, n: int):
        self.fa = list(range(n))
        self.rank = [1] * n

    def find(self, x: int) -> int:
        if self.fa[x] != x:
            self.fa[x] = self.find(self.fa[x])
        return self.fa[x]

    def union(self, x: int, y: int) -> bool:
        fx, fy = self.find(x), self.find(y)
        if fx == fy:
            return False
        if self.rank[fx] < self.rank[fy]:
            fx, fy = fy, fx
        self.rank[fx] += self.rank[fy]
        self.fa[fy] = fx
        return True

质数

1
2
3
4
5
6
7
8
9
10
11
12
13
def eulerSieve(n):
    primes = []
    is_prime = [True] * (n + 1)
    for i in range(2, n + 1):
        if is_prime[i]:
            primes.append(i)
        for p in primes:
            if i * p > n:
                break
            is_prime[i * p] = False
            if i % p == 0:
                break
    return primes

Manachar

half_len[i] 在t中以i为中心扩展的长度，包括自身

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def manacher2(s):
    t = "#".join("^" + s + "$")
    half_len = [0] * (len(t) - 2)
    half_len[1] = 1
    ans = box_m = box_r = 0
    for i in range(2, len(half_len)):
        hl = 1
        if i < box_r:
            hl = min(half_len[box_m * 2 - i], box_r - i)
        while t[i - hl] == t[i + hl]:
            hl += 1
            box_m, box_r = i, i + hl
        half_len[i] = hl
        ans += hl // 2
    return ans

Floyd

查询f[from][to]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def Floyd(graph):
    n = len(graph)

    f = [[inf] * n for _ in range(n)]
    for idx, i in enumerate(graph):
        f[idx][idx] = 1
        for j in i:
            f[j][idx] = 1
            f[idx][j] = 1

    for k in range(n):
        for x in range(n):
            for y in range(n):
                f[x][y] = min(f[x][y], f[x][k] + f[k][y])

Python递归加速

https://blog.csdn.net/liuliangcan/article/details/126958569

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from types import GeneratorType
def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc

二维前缀和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class MatrixSum:
    def __init__(self, matrix: List[List[int]]):
        m, n = len(matrix), len(matrix[0])
        s = [[0] * (n + 1) for _ in range(m + 1)]
        for i, row in enumerate(matrix):
            for j, x in enumerate(row):
                s[i + 1][j + 1] = s[i + 1][j] + s[i][j + 1] - s[i][j] + x
        self.s = s

    # Sum [(r1,c1), (r2,c2))
    def query(self, r1: int, c1: int, r2: int, c2: int) -> int:
        return self.s[r2][c2] - self.s[r2][c1] - self.s[r1][c2] + self.s[r1][c1]

    # Sum [(r1,c1), (r2,c2)]
    def query2(self, r1: int, c1: int, r2: int, c2: int) -> int:
        return self.s[r2 + 1][c2 + 1] - self.s[r2 + 1][c1] - self.s[r1][c2 + 1] + self.s[r1][c1]

logTrick

时间复杂度nlogU

1
2
3
4
5
6
def countSubarrays(self, nums: List[int], k: int) -> int:
    for i, x in enumerate(nums):
        for j in range(i - 1, -1, -1):
            if nums[j] & x == nums[j]:
                break
            nums[j] &= x

组合数

C(n, m) == n! / ((n - m)! * m!)

1
2
3
4
5
6
7
N = 300005
factorial = [1] * N
for i in range(2, N):
    factorial[i] = (factorial[i - 1] * i) % MOD
def C(n, m):
    if n < m: return 0
    return (factorial[n] * pow(factorial[n - m] * factorial[m], MOD - 2, MOD)) % MOD
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Factorial:
    def __init__(self, N, mod) -> None:
        N += 1
        self.mod = mod
        self.f = [1 for _ in range(N)]
        self.g = [1 for _ in range(N)]
        for i in range(1, N):
            self.f[i] = self.f[i - 1] * i % self.mod
        self.g[-1] = pow(self.f[-1], mod - 2, mod)
        for i in range(N - 2, -1, -1):
            self.g[i] = self.g[i + 1] * (i + 1) % self.mod

    def fac(self, n):
        ''' n! '''
        return self.f[n]

    def fac_inv(self, n):
        ''' n! ^ (mod - 2) % mod '''
        return self.g[n]

    def combi(self, n, m):
        ''' C(n, m) '''
        if n < m or m < 0 or n < 0: return 0
        return self.f[n] * self.g[m] % self.mod * self.g[n - m] % self.mod

    def permu(self, n, m):
        ''' A(n, m) '''
        if n < m or m < 0 or n < 0: return 0
        return self.f[n] * self.g[n - m] % self.mod

    def catalan(self, n):
        return (self.combi(2 * n, n) - self.combi(2 * n, n - 1)) % self.mod

    def inv(self, n):
        return self.f[n - 1] * self.g[n] % self.mod

Tarjan

Cut Edge

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Neighbor:
    __slots__ = ('to', 'eid')

    def __init__(self, to, eid):
        self.to = to
        self.eid = eid

def findBridges(n, edges):
    g = [[] for _ in range(n)]
    for i, (v, w) in enumerate(edges):
        g[v].append(Neighbor(w, i))
        g[w].append(Neighbor(v, i))

    is_bridge = [False] * len(edges)
    dfn = [0] * n
    dfs_clock = [0]

    def tarjan(v, fid):
        dfs_clock[0] += 1
        dfn[v] = dfs_clock[0]
        low_v = dfn[v]
        for e in g[v]:
            w, eid = e.to, e.eid
            if dfn[w] == 0:
                low_w = tarjan(w, eid)
                low_v = min(low_v, low_w)
                if low_w > dfn[v]:
                    is_bridge[eid] = True
            elif eid != fid:
                low_v = min(low_v, dfn[w])
        return low_v

    for v in range(n):
        if dfn[v] == 0:
            tarjan(v, -1)

    bridge_eids = [eid for eid, b in enumerate(is_bridge) if b]

    return is_bridge, bridge_eids

Cut Vertices

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def findCutVertices(n, g):
    is_cut = [False] * n
    dfn = [0] * n
    dfs_clock = 0

    def tarjan(v, fa):
        nonlocal dfs_clock
        dfs_clock += 1
        dfn[v] = dfs_clock
        low_v = dfs_clock
        child_cnt = 0
        for w in g[v]:
            if dfn[w] == 0:
                child_cnt += 1
                low_w = tarjan(w, v)
                low_v = min(low_v, low_w)
                if low_w >= dfn[v]:
                    is_cut[v] = True
            elif w != fa:
                low_v = min(low_v, dfn[w])
        if fa == -1 and child_cnt == 1:
            is_cut[v] = False
        return low_v

    for v in range(n):
        if dfn[v] == 0:
            tarjan(v, -1)

    cuts = [v for v, isCut in enumerate(is_cut) if isCut]

    return cuts

SCC

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
def tarjanSCC(graph):
    def tarjan(v):
        nonlocal dfs_clock
        dfs_clock += 1
        dfn[v] = dfs_clock
        low_v = dfs_clock
        stack.append(v)

        for w in graph[v]:
            if dfn[w] == 0:
                low_w = tarjan(w)
                low_v = min(low_v, low_w)
            else:
                low_v = min(low_v, dfn[w])

        if dfn[v] == low_v:
            scc = []
            while True:
                w = stack.pop()
                dfn[w] = inf
                scc.append(w)
                if w == v:
                    break
            all_scc.append(scc)

        return low_v

    n = len(graph)
    all_scc = []
    dfn = [0] * n
    dfs_clock = 0
    stack = []
    for i in range(n):
        if dfn[i] == 0:
            tarjan(i)

    all_scc.reverse()
    sid = [0] * n
    for i, scc in enumerate(all_scc):
        for v in scc:
            sid[v] = i

    g2 = [[] for _ in range(len(all_scc))]
    deg = [0] * len(all_scc)

    for v in range(n):
        v_comp = sid[v]
        for w in graph[v]:
            w_comp = sid[w]
            if v_comp != w_comp:
                g2[v_comp].append(w_comp)
                deg[w_comp] += 1

    return all_scc, sid

字符串哈希

单模

1
2
3
4
5
6
7
8
9
10
11
n = len(s)
MOD = 1070777777
BASE = randint(int(8E8), int(9E8))
pw = [1] + [0] * n
hs = [0] * (n + 1)
for i, x in enumerate(s):
    pw[i + 1] = pw[i] * BASE % MOD
    hs[i + 1] = (hs[i] * BASE + ord(x)) % MOD
def subHash(l, r):
    # [l, r)
    return (hs[r] - hs[l] * pw[r - l]) % MOD

双模

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
n = len(s)
MOD1 = 1070777777
MOD2 = 1000000007
BASE = randint(int(8E8), int(9E8))
pw1 = [1] + [0] * n
pw2 = [1] + [0] * n
hs1 = [0] * (n + 1)
hs2 = [0] * (n + 1)
for i, x in enumerate(s):
    pw1[i + 1] = pw1[i] * BASE % MOD1
    pw2[i + 1] = pw2[i] * BASE % MOD2
    hs1[i + 1] = (hs1[i] * BASE + ord(x)) % MOD1
    hs2[i + 1] = (hs2[i] * BASE + ord(x)) % MOD2
def subHash(l, r):
    # [l, r)
    return ((hs1[r] - hs1[l] * pw1[r - l]) % MOD1) * ((hs2[r] - hs2[l] * pw2[r - l]) % MOD2)

矩阵快速幂

1
2
3
4
5
6
7
8
9
10
11
12
# 矩阵乘法
def mul(a, b):
    return [[sum(x * y for x, y in zip(row, col)) % MOD for col in zip(*b)] for row in a]
# a矩阵 n指数 f0初始向量
def quickPow(a, n, f0):
    res = f0
    while n:
        if n & 1:
            res = mul(a, res)
        a = mul(a, a)
        n >>= 1
    return res

dfn

In[i] < In[j] <= Out[j]说明j在i的子树内

1
2
3
4
5
6
7
8
9
10
11
12
In = [0] * n
Out = [0] * n
T = 0
def DFS(i, fa):
    nonlocal T
    T += 1
    In[i] = T
    for j in g[i]:
        if j != fa:
            DFS(j, i)
    Out[i] = T
DFS(0, -1)

杂项

1
2
3
4
5
6
7
# a XOR b = (a AND b) XOR (a OR b)
# a + b = (a XOR b) + 2(a AND b)
# a + b = (a OR b) + (a AND b)
# x / y % MOD = x * pow(y, MOD - 2, MOD) % MOD
# m个相同的球放入n个不同的盒子中，允许空盒，方案数为C(m + n - 1, m) (隔板法)
# 树的直径: v1广搜到最远节点v2 v2广搜到最远节点v3，d=(v2, v3)
# accumulate(range(x+1), XOR) ans=[x, 1, x + 1, 0][x % 4]
License

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

快来参与讨论吧~

pv:
uv: