{
"模板": {
"prefix": "py_model",
"body": [
"# $TM_FILEPATH ${CURRENT_YEAR}-${CURRENT_MONTH}-${CURRENT_DATE} by 777",
"import sys",
"sys.setrecursionlimit(100000)",
"input=lambda:sys.stdin.readline().strip()",
"# write=lambda x:sys.stdout.write(str(x)+'\\n')",
"# from decimal import Decimal",
"# from datetime import datetime,timedelta",
"# from random import randint",
"# from copy import deepcopy",
"from collections import *",
"# from heapq import heapify,heappush,heappop",
"# from bisect import bisect_left,bisect,insort",
"# from math import inf,sqrt,gcd,pow,ceil,floor,log,log2,log10,pi,sin,cos,tan,asin,acos,atan",
"# from functools import cmp_to_key,reduce",
"# from operator import or_,xor,add,mul",
"# from itertools import permutations,combinations,accumulate",
"sint = lambda: int(input())",
"mint = lambda: map(int, input().split())",
"lint = lambda: list(map(int, input().split()))",
"",
"def solve():",
" $1",
"",
"",
"",
"",
"",
"",
"if __name__ == '__main__':",
" #t=int(input())",
" #for _ in range(t):",
" # solve()",
"",
" solve()"
],
"description": "模板"
},
"求质因数个数": {
"prefix": "divdie",
"body": [
"def divide(n):",
" ans = []",
" i = 2",
" while i <= n // i:",
" if n % i == 0:",
" cnt = 0",
" while n % i == 0:",
" cnt += 1",
" n //= i",
" ans.append((i, cnt))",
" i += 1",
" if n > 1:",
" ans.append((n, 1))",
" return ans"
],
"description": "求质因数个数"
},
"判断质数": {
"prefix": "ispirme",
"body": [
"def is_prime(n):",
" if n < 2:",
" return False",
" i = 2",
" while i <=n // i:",
" if n % i == 0:",
" return False",
" i += 1",
" return True"
],
"description": "判断质数"
},
"primes": {
"prefix": "primes",
"body": [
"pri = []",
"not_prime = [False] * N",
"",
"def pre(n):",
" for i in range(2, n + 1):",
" if not not_prime[i]:",
" pri.append(i)",
" for pri_j in pri:",
" if i * pri_j > n:",
" break",
" not_prime[i * pri_j] = True",
" if i % pri_j == 0:",
" break"
],
"description": "primes"
},
"组合数": {
"prefix": "comb",
"body": [
"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):",
" return self.f[n]",
"",
" def fac_inv(self, n):",
" return self.g[n]",
"",
" def comb(self, 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):",
" 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.comb(2 * n, n) - self.comb(2 * n, n - 1)) % self.mod",
"",
" def inv(self, n):",
" return self.f[n - 1] * self.g[n] % self.mod"
],
"description": "组合数"
},
"DSU": {
"prefix": "DSU",
"body": [
"class DSU:",
" def __init__(self, n):",
" self.parent = list(range(n))",
" self.size = [1] * n",
" self.n = n",
" self.setCount = n",
"",
" def find(self, x):",
" if self.parent[x] != x:",
" self.parent[x] = self.find(self.parent[x])",
" return self.parent[x]",
"",
" def union(self, x, y):",
" x, y = self.find(x), self.find(y)",
" if x == y:",
" return False",
" if self.size[x] < self.size[y]:",
" x, y = y, x",
" self.parent[y] = x",
" self.size[x] += self.size[y]",
" self.setCount -= 1",
" return True",
"",
" def connected(self, x, y):",
" x, y = self.find(x), self.find(y)",
" return x == y"
],
"description": "DSU"
},
"树状数组": {
"prefix": "Fenwick",
"body": [
"# 左闭右闭",
"class FenWick:",
" def __init__(self, n: int):",
" self.n = n",
" self.tr = [0 for _ in range(n + 1)]",
"",
" def sum(self, i: int):",
" i += 1",
" s = 0",
" while i >= 1:",
" s += self.tr[i]",
" i &= i - 1",
" return s",
"",
" def rangeSum(self, l: int, r: int):",
" return self.sum(r) - self.sum(l - 1)",
"",
" def add(self, i: int, val: int):",
" i += 1",
" while i <= self.n:",
" self.tr[i] += val",
" i += i & -i"
],
"description": "树状数组"
},
"LCA": {
"prefix": "LCA",
"body": [
"class TreeAncestor:",
" def __init__(self, edges: List[List[int]]):",
" n = len(edges) + 1",
" m = n.bit_length()",
" g = [[] for _ in range(n)]",
" for x, y in edges: # 节点编号从 0 开始",
" g[x].append(y)",
" g[y].append(x)",
"",
" depth = [0] * n",
" pa = [[-1] * m for _ in range(n)]",
" def dfs(x: int, fa: int) -> None:",
" pa[x][0] = fa",
" for y in g[x]:",
" if y != fa:",
" depth[y] = depth[x] + 1",
" dfs(y, x)",
" dfs(0, -1)",
"",
" for i in range(m - 1):",
" for x in range(n):",
" if (p := pa[x][i]) != -1:",
" pa[x][i + 1] = pa[p][i]",
" self.depth = depth",
" self.pa = pa",
"",
" def get_kth_ancestor(self, node: int, k: int) -> int:",
" for i in range(k.bit_length()):",
" if (k >> i) & 1: # k 二进制从低到高第 i 位是 1",
" node = self.pa[node][i]",
" return node",
"",
" # 返回 x 和 y 的最近公共祖先（节点编号从 0 开始）",
" def get_lca(self, x: int, y: int) -> int:",
" if self.depth[x] > self.depth[y]:",
" x, y = y, x",
" # 使 y 和 x 在同一深度",
" y = self.get_kth_ancestor(y, self.depth[y] - self.depth[x])",
" if y == x:",
" return x",
" for i in range(len(self.pa[x]) - 1, -1, -1):",
" px, py = self.pa[x][i], self.pa[y][i]",
" if px != py:",
" x, y = px, py # 同时上跳 2**i 步",
" return self.pa[x][0]",
""
],
"description": "LCA"
},
"Z函数": {
"prefix": "Zfunc",
"body": [
"def z_function(s):",
" n = len(s)",
" z = [0] * n",
" l, r = 0, 0",
" for i in range(1, n):",
" if i <= r and z[i - l] < r - i + 1:",
" z[i] = z[i - l]",
" else:",
" z[i] = max(0, r - i + 1)",
" while i + z[i] < n and s[z[i]] == s[i + z[i]]:",
" z[i] += 1",
" if i + z[i] - 1 > r:",
" l = i",
" r = i + z[i] - 1",
" return z"
],
"description": "Z函数"
},
"SortedList": {
"prefix": "SortedList",
"body": [
"",
"class SortedList:",
" def __init__(self, iterable=[], _load=200):",
" \"\"\"Initialize sorted list instance.\"\"\"",
" values = sorted(iterable)",
" self._len = _len = len(values)",
" self._load = _load",
" self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]",
" self._list_lens = [len(_list) for _list in _lists]",
" self._mins = [_list[0] for _list in _lists]",
" self._fen_tree = []",
" self._rebuild = True",
"",
" def _fen_build(self):",
" \"\"\"Build a fenwick tree instance.\"\"\"",
" self._fen_tree[:] = self._list_lens",
" _fen_tree = self._fen_tree",
" for i in range(len(_fen_tree)):",
" if i | i + 1 < len(_fen_tree):",
" _fen_tree[i | i + 1] += _fen_tree[i]",
" self._rebuild = False",
"",
" def _fen_update(self, index, value):",
" \"\"\"Update `fen_tree[index] += value`.\"\"\"",
" if not self._rebuild:",
" _fen_tree = self._fen_tree",
" while index < len(_fen_tree):",
" _fen_tree[index] += value",
" index |= index + 1",
"",
" def _fen_query(self, end):",
" \"\"\"Return `sum(_fen_tree[:end])`.\"\"\"",
" if self._rebuild:",
" self._fen_build()",
"",
" _fen_tree = self._fen_tree",
" x = 0",
" while end:",
" x += _fen_tree[end - 1]",
" end &= end - 1",
" return x",
"",
" def _fen_findkth(self, k):",
" \"\"\"Return a pair of (the largest `idx` such that `sum(_fen_tree[:idx]) <= k`, `k - sum(_fen_tree[:idx])`).\"\"\"",
" _list_lens = self._list_lens",
" if k < _list_lens[0]:",
" return 0, k",
" if k >= self._len - _list_lens[-1]:",
" return len(_list_lens) - 1, k + _list_lens[-1] - self._len",
" if self._rebuild:",
" self._fen_build()",
"",
" _fen_tree = self._fen_tree",
" idx = -1",
" for d in reversed(range(len(_fen_tree).bit_length())):",
" right_idx = idx + (1 << d)",
" if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:",
" idx = right_idx",
" k -= _fen_tree[idx]",
" return idx + 1, k",
"",
" def _delete(self, pos, idx):",
" \"\"\"Delete value at the given `(pos, idx)`.\"\"\"",
" _lists = self._lists",
" _mins = self._mins",
" _list_lens = self._list_lens",
"",
" self._len -= 1",
" self._fen_update(pos, -1)",
" del _lists[pos][idx]",
" _list_lens[pos] -= 1",
"",
" if _list_lens[pos]:",
" _mins[pos] = _lists[pos][0]",
" else:",
" del _lists[pos]",
" del _list_lens[pos]",
" del _mins[pos]",
" self._rebuild = True",
"",
" def _loc_left(self, value):",
" \"\"\"Return an index pair that corresponds to the first position of `value` in the sorted list.\"\"\"",
" if not self._len:",
" return 0, 0",
"",
" _lists = self._lists",
" _mins = self._mins",
"",
" lo, pos = -1, len(_lists) - 1",
" while lo + 1 < pos:",
" mi = (lo + pos) >> 1",
" if value <= _mins[mi]:",
" pos = mi",
" else:",
" lo = mi",
"",
" if pos and value <= _lists[pos - 1][-1]:",
" pos -= 1",
"",
" _list = _lists[pos]",
" lo, idx = -1, len(_list)",
" while lo + 1 < idx:",
" mi = (lo + idx) >> 1",
" if value <= _list[mi]:",
" idx = mi",
" else:",
" lo = mi",
"",
" return pos, idx",
"",
" def _loc_right(self, value):",
" \"\"\"Return an index pair that corresponds to the last position of `value` in the sorted list.\"\"\"",
" if not self._len:",
" return 0, 0",
"",
" _lists = self._lists",
" _mins = self._mins",
"",
" pos, hi = 0, len(_lists)",
" while pos + 1 < hi:",
" mi = (pos + hi) >> 1",
" if value < _mins[mi]:",
" hi = mi",
" else:",
" pos = mi",
"",
" _list = _lists[pos]",
" lo, idx = -1, len(_list)",
" while lo + 1 < idx:",
" mi = (lo + idx) >> 1",
" if value < _list[mi]:",
" idx = mi",
" else:",
" lo = mi",
"",
" return pos, idx",
"",
" def add(self, value):",
" \"\"\"Add `value` to sorted list.\"\"\"",
" _load = self._load",
" _lists = self._lists",
" _mins = self._mins",
" _list_lens = self._list_lens",
"",
" self._len += 1",
" if _lists:",
" pos, idx = self._loc_right(value)",
" self._fen_update(pos, 1)",
" _list = _lists[pos]",
" _list.insert(idx, value)",
" _list_lens[pos] += 1",
" _mins[pos] = _list[0]",
" if _load + _load < len(_list):",
" _lists.insert(pos + 1, _list[_load:])",
" _list_lens.insert(pos + 1, len(_list) - _load)",
" _mins.insert(pos + 1, _list[_load])",
" _list_lens[pos] = _load",
" del _list[_load:]",
" self._rebuild = True",
" else:",
" _lists.append([value])",
" _mins.append(value)",
" _list_lens.append(1)",
" self._rebuild = True",
"",
" def discard(self, value):",
" \"\"\"Remove `value` from sorted list if it is a member.\"\"\"",
" _lists = self._lists",
" if _lists:",
" pos, idx = self._loc_right(value)",
" if idx and _lists[pos][idx - 1] == value:",
" self._delete(pos, idx - 1)",
"",
" def remove(self, value):",
" \"\"\"Remove `value` from sorted list; `value` must be a member.\"\"\"",
" _len = self._len",
" self.discard(value)",
" if _len == self._len:",
" raise ValueError('{0!r} not in list'.format(value))",
"",
" def pop(self, index=-1):",
" \"\"\"Remove and return value at `index` in sorted list.\"\"\"",
" pos, idx = self._fen_findkth(self._len + index if index < 0 else index)",
" value = self._lists[pos][idx]",
" self._delete(pos, idx)",
" return value",
"",
" def bisect_left(self, value):",
" \"\"\"Return the first index to insert `value` in the sorted list.\"\"\"",
" pos, idx = self._loc_left(value)",
" return self._fen_query(pos) + idx",
"",
" def bisect_right(self, value):",
" \"\"\"Return the last index to insert `value` in the sorted list.\"\"\"",
" pos, idx = self._loc_right(value)",
" return self._fen_query(pos) + idx",
"",
" def count(self, value):",
" \"\"\"Return number of occurrences of `value` in the sorted list.\"\"\"",
" return self.bisect_right(value) - self.bisect_left(value)",
"",
" def __len__(self):",
" \"\"\"Return the size of the sorted list.\"\"\"",
" return self._len",
"",
" def __getitem__(self, index):",
" \"\"\"Lookup value at `index` in sorted list.\"\"\"",
" pos, idx = self._fen_findkth(self._len + index if index < 0 else index)",
" return self._lists[pos][idx]",
"",
" def __delitem__(self, index):",
" \"\"\"Remove value at `index` from sorted list.\"\"\"",
" pos, idx = self._fen_findkth(self._len + index if index < 0 else index)",
" self._delete(pos, idx)",
"",
" def __contains__(self, value):",
" \"\"\"Return true if `value` is an element of the sorted list.\"\"\"",
" _lists = self._lists",
" if _lists:",
" pos, idx = self._loc_left(value)",
" return idx < len(_lists[pos]) and _lists[pos][idx] == value",
" return False",
"",
" def __iter__(self):",
" \"\"\"Return an iterator over the sorted list.\"\"\"",
" return (value for _list in self._lists for value in _list)",
"",
" def __reversed__(self):",
" \"\"\"Return a reverse iterator over the sorted list.\"\"\"",
" return (value for _list in reversed(self._lists) for value in reversed(_list))",
"",
" def __repr__(self):",
" \"\"\"Return string representation of sorted list.\"\"\"",
" return 'SortedList({0})'.format(list(self))",
"",
""
],
"description": "SortedList"
},
"spfa": {
"prefix": "spfa",
"body": [
"def spfa(u, n, g) -> int:",
" q = deque()",
" q.append(u)",
" vis = set()",
" dist = defaultdict(lambda : inf)",
" vis.add(u)",
" dist[u] = 0",
" while q:",
" t = q.popleft()",
" vis.remove(t)",
" for j, d in g[t]:",
" if dist[j] > dist[t] + d:",
" dist[j] = dist[t] + d",
" if j not in vis:",
" vis.add(j)",
" q.append(j)",
" return dist[n]"
],
"description": "spfa"
},
"dij": {
"prefix": "dij",
"body": [
"def dij(u, n, g) -> int:",
" q = [(0, u)] # 距离 顶点",
" vis = set()",
" dist = defaultdict(lambda : inf)",
" dist[1] = 0",
" while q:",
" d, u = heappop(q)",
" if u in vis:",
" continue",
" vis.add(u)",
" for j, d in g[u]:",
" if j not in vis and dist[j] > dist[u] + d:",
" dist[j] = dist[u] + d",
" heappush(q, (dist[j], j))",
" return dist[n]"
],
"description": "dij"
},
"字符串哈希": {
"prefix": "stringhaxi",
"body": [
"class StringHash:",
" def __init__(self, s):",
" n = len(s)",
" self.base = 131",
" self.mod = 10 ** 13 + 7",
" self.h = h = [0] * (n + 1)",
" self.p = p = [1] * (n + 1)",
" for i in range(1, n + 1):",
" p[i] = p[i - 1] * base % mod",
" h[i] = h[i - 1] * base + ord(s[i - 1])",
" h[i] %= mod",
"",
" def get_hash(self, l, r):",
" res = self.h[r] - self.h[l] * self.p[r - l]",
" return res % mod"
],
"description": "字符串哈希"
},
"二维前缀和": {
"prefix": "qianzhui",
"body": [
"s = [[0 for j in range(m + 1)] for i in range(n + 1)]",
"for i in range(1, n + 1):",
" for j in range (1, m + 1):",
" s[i][j] += s[i - 1][j] + a[i][j] + s[i][j - 1] - s[i - 1][j - 1]",
"",
"",
"for _ in range(q):",
" x1, y1, x2, y2 = mint()",
" ans = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]",
" print(ans)"
],
"description": "二维前缀和"
},
"二维差分": {
"prefix": "chafen",
"body": [
"for i in range(1, n + 1):",
" for j in range(1, m + 1):",
" b[i][j] = a[i][j] - a[i - 1][j] - a[i][j - 1] + a[i - 1][j - 1]",
"for i in range(q):",
" x1, y1, x2, y2, c = mint()",
" b[x1][y1] += c",
" b[x1][y2 + 1] -= c",
" b[x2 + 1][y1] -= c",
" b[x2 + 1][y2 + 1] += c",
"for i in range(1, n + 1):",
" for j in range(1, m + 1):",
" a[i][j] = b[i][j] + a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1]",
" print(a[i][j], end = ' ')",
" print()"
],
"description": "二维差分"
},
"最小生成树": {
"prefix": "kurs",
"body": [
"def kruskal():",
" dsu = DSU(n)",
" edges.sort(key = lambda x : x[2])",
" res = 0",
" for u, v, w in edges:",
" if dsu.same(u, v):",
" continue",
" dsu.merge(u, v)",
" res += w",
" return res if dsu.n == 1 else inf"
],
"description": "最小生成树"
}
}
https://pan.baidu.com/s/1Z2OdNg12GkvnQiafRoO7Uw
