Pythonライブラリ
| 投稿者 | detteiuu |
|---|---|
| 言語 | PyPy3 |
| 更新日時 (JST) | 2026-10-17 19:32:56 |
| サイズ | 207,400 Byte |
| 参照URL | |
日時はサーバーが記録したものです。更新すると更新日時が変わるので、不都合がある場合は新しく投稿してください。
・再帰
import sys
sys.setrecursionlimit(10**6)
import pypyjit
pypyjit.set_param('max_unroll_recursion=-1')
デコレータ
from types import GeneratorType
def bootstrap(f, stack=[]):
def wrappedfunc(*args, **kwargs):
if stack:
return f(*args, **kwargs)
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. @bootstrap を再帰関数の前につける
2. returnはyieldと書く
3. 自身を呼び出す場合は先頭にyieldと書く（計算式の中などで呼び出す場合は括弧で囲む [(yield func(a))]）
4. 戻り値がない場合でも、最後にyieldと書く
5. 再帰上限の変更は書く必要がない
・実行速度の計測
import time
start = time.time()
end = time.time()
print(end - start)
・UnionFind
class UnionFind:
def __init__(self,n):
self.n = n
self.parent_size = [-1]*n
def leader(self,a):
if self.parent_size[a] < 0:
return a
self.parent_size[a] = self.leader(self.parent_size[a])
return self.parent_size[a]
def merge(self,a,b):
x, y = self.leader(a), self.leader(b)
if x == y:
return
if abs(self.parent_size[x]) < abs(self.parent_size[y]):
x, y = y, x
self.parent_size[x] += self.parent_size[y]
self.parent_size[y] = x
return
def same(self,a,b):
return self.leader(a) == self.leader(b)
def size(self,a):
return abs(self.parent_size[self.leader(a)])
def groups(self):
result = [[] for _ in range(self.n)]
for i in range(self.n):
result[self.leader(i)].append(i)
return [r for r in result if r != []]
・素数判定
def isPrime(n):
if n <= 1:
return False
else:
i = 2
while i**2 <= n:
if n%i == 0:
return False
i += 1
return True
・エラトステネスのふるい
def eratosthenes(n):
sieve = [True] * (n + 1)
for i in range(int(n**0.5) + 1):
if i < 2:
sieve[i] = False
elif sieve[i]:
for j in range(i, n//i + 1):
sieve[i * j] = False
ans = []
for i in range(n+1):
if sieve[i]:
ans.append(i)
return ans
・10進数→n進数
def base_n(num_10,n):
str_n = ''
while num_10:
if num_10%n>=10:
return -1
str_n += str(num_10%n)
num_10 //= n
return int(str_n[::-1])
・ユークリッドの互除法
def gcd(a, b):
r = a % b
while r != 0:
a, b = b, r
r = a % b
return b
・素因数分解
from math import isqrt
def factorization(n):
arr = []
temp = n
for i in range(2, isqrt(n)+1):
if temp%i == 0:
cnt = 0
while temp%i == 0:
cnt += 1
temp //= i
arr.append([i, cnt])
if temp != 1:
arr.append([temp, 1])
if arr == []:
arr.append([n, 1])
return arr
・約数列挙
def divisor(n):
ans = []
for i in range(1, int(n**0.5)+1):
if n % i == 0:
ans.append(i)
if i*i != n:
ans.append(n//i)
return ans
・２点間の距離
def distance(x1, y1, x2, y2):
return ((x2-x1)**2 + (y2-y1)**2) ** 0.5
（比較演算をする場合はルートを外してかわりに反対側を2乗する）
・トリミング
def trimming(A):
minH = len(A)
maxH = 0
minW = len(A[0])
maxW = 0
for i in range(len(A)):
for j in range(len(A[0])):
if A[i][j] == "#":
minH = min(i, minH)
maxH = max(i, maxH)
minW = min(j, minW)
maxW = max(j, maxW)
a = []
for i in range(minH, maxH+1):
a.append(A[i][minW:maxW+1])
return a
・回転（時計回り）
def rotateR(A):
return list(map(list, zip(*A[::-1])))
・回転（反時計回り）
def rotateL(A):
return list(map(list, zip(*A)))[::-1]
・ランダムアクセスがO(1)のdeque
class Deque:
def __init__(self, src_arr=[], max_size=300000):
self.N = max(max_size, len(src_arr)) + 1
self.buf = list(src_arr) + [None] * (self.N - len(src_arr))
self.head = 0
self.tail = len(src_arr)
def __index(self, i):
l = len(self)
if not -l <= i < l: raise IndexError('index out of range: ' + str(i))
if i < 0:
i += l
return (self.head + i) % self.N
def __extend(self):
ex = self.N - 1
self.buf[self.tail+1 : self.tail+1] = [None] * ex
self.N = len(self.buf)
if self.head > 0:
self.head += ex
def is_full(self):
return len(self) >= self.N - 1
def is_empty(self):
return len(self) == 0
def append(self, x):
if self.is_full(): self.__extend()
self.buf[self.tail] = x
self.tail += 1
self.tail %= self.N
def appendleft(self, x):
if self.is_full(): self.__extend()
self.buf[(self.head - 1) % self.N] = x
self.head -= 1
self.head %= self.N
def pop(self):
if self.is_empty(): raise IndexError('pop() when buffer is empty')
ret = self.buf[(self.tail - 1) % self.N]
self.tail -= 1
self.tail %= self.N
return ret
def popleft(self):
if self.is_empty(): raise IndexError('popleft() when buffer is empty')
ret = self.buf[self.head]
self.head += 1
self.head %= self.N
return ret
def __len__(self):
return (self.tail - self.head) % self.N
def __getitem__(self, key):
return self.buf[self.__index(key)]
def __setitem__(self, key, value):
self.buf[self.__index(key)] = value
def __str__(self):
return 'Deque({0})'.format(str(list(self)))
・セグメント木
def op(x, y):
return
class SegTree:
def __init__(self, init_val, op, ide_ele):
n = len(init_val)
self.n = n
self.op = op
self.ide_ele = ide_ele
self.num = 1 << (n - 1).bit_length()
self.tree = [ide_ele] * 2 * self.num
for i in range(n):
self.tree[self.num + i] = init_val[i]
for i in range(self.num - 1, 0, -1):
self.tree[i] = self.op(self.tree[2 * i], self.tree[2 * i + 1])
def update(self, k, x):
k += self.num
self.tree[k] = x
while k > 1:
l, r = k, k^1
if l > r:
l, r = r, l
self.tree[k >> 1] = self.op(self.tree[l], self.tree[r])
k >>= 1
def query(self, l, r):
res_l = self.ide_ele
res_r = self.ide_ele
l += self.num
r += self.num
while l < r:
if l & 1:
res_l = self.op(res_l, self.tree[l])
l += 1
if r & 1:
res_r = self.op(self.tree[r - 1], res_r)
l >>= 1
r >>= 1
return self.op(res_l, res_r)
def __getitem__(self, n):
return self.tree[self.num+n]
def List(self):
return self.tree[self.num:self.num+self.n]
def max_right(self, l, f, limit):
if l == self.n:
return self.n
l += self.num
sm = self.ide_ele
while True:
while l%2 == 0:
l >>= 1
if not f(self.op(sm, self.tree[l]), limit):
while l < self.num:
l <<= 1
if f(self.op(sm, self.tree[l]), limit):
sm = self.op(sm, self.tree[l])
l += 1
return l-self.num
sm = self.op(sm, self.tree[l])
l += 1
if l & -l == l:
break
return self.n
def min_left(self, r, f, limit):
if r == 0:
return 0
r += self.num
sm = self.ide_ele
while True:
r -= 1
while r > 1 and r%2 == 1:
r >>= 1
if not f(self.op(self.tree[r], sm), limit):
while r < self.num:
r = 2*r+1
if f(self.op(self.tree[r], sm), limit):
sm = self.op(self.tree[r], sm)
r -= 1
return r+1-self.num
sm = self.op(self.tree[r], sm)
if r & -r == r:
break
return 0
〇使い方
1. 初期化用のリストを用意
2. 区間に行う操作をsegfuncに書き込む
・最小値 min(x, y)
・最大値 max(x, y)
・区間和 x + y
・区間積 x * y
・最大公約数 math.gcd(x, y)
3. 生成
seg = SegTree(リスト, segfunc, (単位元))
・単位元
・最小値 float('inf')
・最大値 -float('inf')
・区間和 0
・区間積 1
・最大公約数 0
4. 操作
0-index
・更新
seg.update(k, x) k番目の要素をxに更新
・区間の操作の結果を取得
seg.query(l, r) l以上r未満の区間から値を取得
・ダイクストラ法
def dijkstra(start):
INF = 10**18
dist = [INF]*N
dist[start] = 0
visited = [False]*N
que = [(0, start)]
while que:
d, now = heappop(que)
if visited[now]:
continue
visited[now] = True
for next, weight in G[now]:
if dist[now]+weight < dist[next]:
dist[next] = dist[now]+weight
heappush(que, (dist[next], next))
return dist
・Ford-Fulkerson
class maxflow_edge:
def __init__(self, to, cap, rev):
self.to = to
self.cap = cap
self.rev = rev
@bootstrap
def dfs(pos, goal, F, G, visited):
if pos == goal:
yield F
visited[pos] = True
for e in G[pos]:
if not visited[e.to] and e.cap > 0:
flow = yield dfs(e.to, goal, min(F, e.cap), G, visited)
if flow >= 1:
e.cap -= flow
G[e.to][e.rev].cap += flow
yield flow
yield 0
def maxflow(s, t, N):
G = [[] for i in range(N)]
for a, b, c in edge:
G[a].append(maxflow_edge(b, c, len(G[b])))
G[b].append(maxflow_edge(a, 0, len(G[a])-1))
total_flow = 0
while True:
visited = [False]*N
F = dfs(s, t, INF, G, visited)
if F > 0:
total_flow += F
else:
break
return total_flow
・逆元
def inverse(n, d):
return n * pow(d, -1, MOD) % MOD
・遅延セグメント木
〇区間加算用
def segfunc(x,y):
return
class LazySegTree_RAQ:
def __init__(self,init_val,segfunc,ide_ele):
n = len(init_val)
self.segfunc = segfunc
self.ide_ele = ide_ele
self.num = 1<<(n-1).bit_length()
self.tree = [ide_ele]*2*self.num
self.lazy = [0]*2*self.num
for i in range(n):
self.tree[self.num+i] = init_val[i]
for i in range(self.num-1,0,-1):
self.tree[i] = self.segfunc(self.tree[2*i], self.tree[2*i+1])
def gindex(self,l,r):
l += self.num
r += self.num
lm = l>>(l&-l).bit_length()
rm = r>>(r&-r).bit_length()
ans = []
while r>l:
if l<=lm:
ans.append(l)
if r<=rm:
ans.append(r)
r >>= 1
l >>= 1
while l:
ans.append(l)
l >>= 1
return ans
def propagates(self,ids):
for i in reversed(ids):
v = self.lazy[i]
if v==0:
continue
self.lazy[i] = 0
self.lazy[2*i] += v
self.lazy[2*i+1] += v
self.tree[2*i] += v
self.tree[2*i+1] += v
def add(self,l,r,x):
ids = self.gindex(l,r)
l += self.num
r += self.num
while l<r:
if l&1:
self.lazy[l] += x
self.tree[l] += x
l += 1
if r&1:
self.lazy[r-1] += x
self.tree[r-1] += x
r >>= 1
l >>= 1
for i in ids:
self.tree[i] = self.segfunc(self.tree[2*i], self.tree[2*i+1]) + self.lazy[i]
def query(self,l,r):
self.propagates(self.gindex(l,r))
res = self.ide_ele
l += self.num
r += self.num
while l<r:
if l&1:
res = self.segfunc(res,self.tree[l])
l += 1
if r&1:
res = self.segfunc(res,self.tree[r-1])
l >>= 1
r >>= 1
return res
〇区間更新用
def segfunc(x,y):
return
class LazySegTree_RUQ:
def __init__(self,init_val,segfunc,ide_ele):
n = len(init_val)
self.segfunc = segfunc
self.ide_ele = ide_ele
self.num = 1<<(n-1).bit_length()
self.tree = [ide_ele]*2*self.num
self.lazy = [None]*2*self.num
for i in range(n):
self.tree[self.num+i] = init_val[i]
for i in range(self.num-1,0,-1):
self.tree[i] = self.segfunc(self.tree[2*i],self.tree[2*i+1])
def gindex(self,l,r):
l += self.num
r += self.num
lm = l>>(l&-l).bit_length()
rm = r>>(r&-r).bit_length()
ans = []
while r>l:
if l<=lm:
ans.append(l)
if r<=rm:
ans.append(r)
r >>= 1
l >>= 1
while l:
ans.append(l)
l >>= 1
return ans
def propagates(self,ids):
for i in reversed(ids):
v = self.lazy[i]
if v is None:
continue
self.lazy[i] = None
self.lazy[2*i] = v
self.lazy[2*i+1] = v
self.tree[2*i] = v
self.tree[2*i+1] = v
def update(self,l,r,x):
ids = self.gindex(l,r)
self.propagates(ids)
l += self.num
r += self.num
while l<r:
if l&1:
self.lazy[l] = x
self.tree[l] = x
l += 1
if r&1:
self.lazy[r-1] = x
self.tree[r-1] = x
r >>= 1
l >>= 1
for i in ids:
self.tree[i] = self.segfunc(self.tree[2*i], self.tree[2*i+1])
def query(self,l,r):
self.propagates(self.gindex(l,r))
res = self.ide_ele
l += self.num
r += self.num
while l<r:
if l&1:
res = self.segfunc(res,self.tree[l])
l += 1
if r&1:
res = self.segfunc(res,self.tree[r-1])
l >>= 1
r >>= 1
return res
〇使い方
1. 初期化用のリストを用意
2. 区間に行う操作をsegfuncに書き込む
・最小値 min(x, y)
・最大値 max(x, y)
・区間和 x + y
・区間積 x * y
・最大公約数 math.gcd(x, y)
3. 生成
seg = SegTree(リスト, segfunc, (単位元))
・単位元
・最小値 float('inf')
・最大値 -float('inf')
・区間和 0
・区間積 1
・最大公約数 0
4. 操作
0-index
・更新
seg.add(l, r, x) l以上r未満の区間にxを加算
seg.update(l, r, x) l以上r未満の区間をxに更新
・区間の操作の結果を取得
seg.query(l, r) l以上r未満の区間から値を取得
・素数リスト
18625498411672028939
93638244515503437017
15508888921625689043
桁最大の素数
1桁⋅⋅⋅7
2桁⋅⋅⋅97
3桁⋅⋅⋅997
4桁⋅⋅⋅9973
5桁⋅⋅⋅99991
6桁⋅⋅⋅999983
7桁⋅⋅⋅9999991
8桁⋅⋅⋅99999989
9桁⋅⋅⋅999999937
10桁⋅⋅⋅9999999967
11桁⋅⋅⋅99999999977
12桁⋅⋅⋅999999999989
13桁⋅⋅⋅9999999999971
14桁⋅⋅⋅99999999999973
15桁⋅⋅⋅999999999999989
16桁⋅⋅⋅9999999999999937
17桁⋅⋅⋅99999999999999997
18桁⋅⋅⋅999999999999999989
19桁⋅⋅⋅9999999999999999961
20桁⋅⋅⋅99999999999999999989
桁最小の素数
1桁⋅⋅⋅2
2桁⋅⋅⋅11
3桁⋅⋅⋅101
4桁⋅⋅⋅1009
5桁⋅⋅⋅10007
6桁⋅⋅⋅100003
7桁⋅⋅⋅1000003
8桁⋅⋅⋅10000019
9桁⋅⋅⋅100000007
10桁⋅⋅⋅1000000007
11桁⋅⋅⋅10000000019
12桁⋅⋅⋅100000000003
13桁⋅⋅⋅1000000000039
14桁⋅⋅⋅10000000000037
15桁⋅⋅⋅100000000000031
16桁⋅⋅⋅1000000000000037
17桁⋅⋅⋅10000000000000061
18桁⋅⋅⋅100000000000000003
19桁⋅⋅⋅1000000000000000003
20桁⋅⋅⋅10000000000000000051
・強連結成分分解
def scc(N,edges):
M=len(edges)
start=[0]*(N+1)
elist=[0]*M
for e in edges:
start[e[0]+1]+=1
for i in range(1,N+1):
start[i]+=start[i-1]
counter=start[:]
for e in edges:
elist[counter[e[0]]]=e[1]
counter[e[0]]+=1
visited=[]
low=[0]*N
Ord=[-1]*N
ids=[0]*N
NG=[0,0]
def dfs(v):
stack=[(v,-1,0),(v,-1,1)]
while stack:
v,bef,t=stack.pop()
if t:
if bef!=-1 and Ord[v]!=-1:
low[bef]=min(low[bef],Ord[v])
stack.pop()
continue
low[v]=NG[0]
Ord[v]=NG[0]
NG[0]+=1
visited.append(v)
for i in range(start[v],start[v+1]):
to=elist[i]
if Ord[to]==-1:
stack.append((to,v,0))
stack.append((to,v,1))
else:
low[v]=min(low[v],Ord[to])
else:
if low[v]==Ord[v]:
while(True):
u=visited.pop()
Ord[u]=N
ids[u]=NG[1]
if u==v:
break
NG[1]+=1
low[bef]=min(low[bef],low[v])
for i in range(N):
if Ord[i]==-1:
dfs(i)
for i in range(N):
ids[i]=NG[1]-1-ids[i]
group_num=NG[1]
counts=[0]*group_num
for x in ids:
counts[x]+=1
groups=[[] for i in range(group_num)]
for i in range(N):
groups[ids[i]].append(i)
return groups
・拡張ユークリッドの互除法
def extended_euclid(a, b):
if b == 0:
return (1, 0)
else:
xd, yd = extended_euclid(b, a % b)
return (yd, xd - a // b * yd)
・重み付きUnionFind
class WeightedUnionFind:
def __init__(self, n):
self.par = [i for i in range(n)]
self.rank = [0] * n
self.weight = [0] * n
def leader(self, x):
if self.par[x] == x:
return x
else:
y = self.leader(self.par[x])
self.weight[x] += self.weight[self.par[x]]
self.par[x] = y
return y
def merge(self, x, y, w):
rx = self.leader(x)
ry = self.leader(y)
if self.rank[rx] < self.rank[ry]:
self.par[rx] = ry
self.weight[rx] = w - self.weight[x] + self.weight[y]
else:
self.par[ry] = rx
self.weight[ry] = -w - self.weight[y] + self.weight[x]
if self.rank[rx] == self.rank[ry]:
self.rank[rx] += 1
def same(self, x, y):
return self.leader(x) == self.leader(y)
def diff(self, x, y):
return self.weight[x] - self.weight[y]
・3点が同一線上にあるか
def judge(x1, y1, x2, y2, x3, y3):
return (x1-x3)*(y2-y3)-(x2-x3)*(y1-y3) == 0
・全方位木dp
def LRset(n):
for i in range(1, len(G[n])):
L[n][i] = L[n][i-1]+dp[n][i-1]
for i in reversed(range(len(G[n])-1)):
R[n][i] = R[n][i+1]+dp[n][i+1]
L = [[0]*len(G[i]) for i in range(N)]
R = [[0]*len(G[i]) for i in range(N)]
LRset(0)
@bootstrap
def rerooting(n, pre, no):
visited[n] = True
preno = 0
for i in range(len(G[n])):
if G[n][i] == pre:
preno = i
break
dp[n][preno] = L[pre][no]+R[pre][no]+1
LRset(n)
for i in range(len(G[n])):
if not visited[G[n][i]]:
yield rerooting(G[n][i], n, i)
yield
visited = [False]*N
visited[0] = True
for i in range(len(G[0])):
if not visited[G[0][i]]:
rerooting(G[0][i], 0, i)
・Z-algorithm
def z_algo(S):
N = len(S)
A = [0]*N
i = 1; j = 0
A[0] = l = len(S)
while i < l:
while i+j < l and S[j] == S[i+j]:
j += 1
if not j:
i += 1
continue
A[i] = j
k = 1
while l-i > k < j - A[k]:
A[i+k] = A[k]
k += 1
i += k; j -= k
return A
・ローリングハッシュ
class RollingHash:
def __init__(self, S, type):
if type == False:
a = ord("a")-1
else:
a = ord("A")-1
self.hash = [0]
for i in range(len(S)):
self.hash.append((self.hash[-1]*26+(ord(S[i])-a))%MOD)
self.POW = [1]
for i in range(len(S)):
self.POW.append(self.POW[-1]*26%MOD)
def query(self, l, r):
return (self.hash[r]-self.hash[l]*self.POW[r-l])%MOD
・最小共通祖先
class LCA:
def __init__(self, G, root=0):
V = len(G)
self.bit_length = 1
while 1<<self.bit_length < V:
self.bit_length += 1
self.parent = [[-1]*V for _ in range(self.bit_length)]
self.depth = [-1]*V
self.bfs(G, root)
for i in range(self.bit_length-1):
for j in range(V):
if self.parent[i][j] != -1:
self.parent[i+1][j] = self.parent[i][self.parent[i][j]]
def bfs(self, G, root):
self.depth[root] = 0
que = deque()
que.append(root)
while que:
n = que.popleft()
for v in G[n]:
if self.depth[v] == -1:
self.depth[v] = self.depth[n]+1
self.parent[0][v] = n
que.append(v)
def lca(self, a, b):
if self.depth[a] < self.depth[b]:
a, b = b, a
for i in range(self.bit_length):
if (self.depth[a]-self.depth[b]) & 1<<i:
a = self.parent[i][a]
if a == b:
return a
for i in reversed(range(self.bit_length)):
if self.parent[i][a] != self.parent[i][b]:
a = self.parent[i][a]
b = self.parent[i][b]
return self.parent[0][a]
def dist(self, a, b):
return self.depth[a]+self.depth[b]-self.depth[self.lca(a, b)]*2
def is_ancestor(self, u, v):
return self.lca(u, v) == u
def kth_ancestor(self, n, k):
for i in range(self.bit_length):
if 1<<i & k:
n = self.parent[i][n]
if n == -1:
break
return n
def jump(self, u, v):
if u == v:
return u
if self.lca(u, v) == u:
return self.kth_ancestor(v, self.dist(u, v)-1)
else:
return self.parent[0][u]
def jump_k(self, u, v, k):
d = self.dist(u, v)
if d <= k:
return v
lca = self.lca(u, v)
if k <= self.depth[u]-self.depth[lca]:
return self.kth_ancestor(u, k)
else:
return self.kth_ancestor(v, d-k)
def on_path(self, u, v, x):
return self.dist(u, x)+self.dist(x, v) == self.dist(u, v)
def create_path(self, u, v, x):
if self.on_path(u, v, x):
return u, v
if self.on_path(u, x, v):
return u, x
if self.on_path(v, x, u):
return v, x
return -1, -1
・HL分解（辺）
class HLDecomposition:
def __init__(self, N, G, segfunc, ide_ele):
self.N = N
self.G = G
self.segfunc = segfunc
self.ide_ele = ide_ele
self.parent = [-1]*N
self.depth = [0]*N
self.size = [1]*N
self.heavy = [-1]*N
self.visited = [False]*N
self.build1(0)
self.top = [0]*N
self.HLD_G = [0]
self.visited = [False]*N
self.build2(0)
self.HLD_G = self.HLD_G[::-1]
self.node_w = [0]*N
self.node = [N-1]*N
self.make_tree()
def update(self, v, w, weight):
if self.parent[w] == v:
v, w = w, v
elif self.parent[v] != w:
return False
self.Tree.update(self.node[v], weight)
def query(self, l, r):
sml, smr = self.ide_ele, self.ide_ele
while True:
li, ri = self.node[l], self.node[r]
if self.top[l] == self.top[r]:
if self.depth[l] > self.depth[r]:
sml = self.segfunc(sml, self.Tree.query(li, ri))
else:
smr = self.segfunc(self.Tree.query(ri, li), smr)
return self.segfunc(sml, smr)
else:
l_top, r_top = self.top[l], self.top[r]
if self.depth[l_top] > self.depth[r_top]:
sml = self.segfunc(sml, self.Tree.query(li, self.node[l_top]+1))
l = self.parent[l_top]
else:
smr = self.segfunc(self.Tree.query(ri, self.node[r_top]+1), smr)
r = self.parent[r_top]
@bootstrap
def build1(self, n):
self.visited[n] = True
for v, _ in self.G[n]:
if not self.visited[v]:
self.parent[v] = n
self.depth[v] = self.depth[n]+1
self.size[n] += yield self.build1(v)
if self.heavy[n] == -1 or self.size[self.heavy[n]] < self.size[v]:
self.heavy[n] = v
yield self.size[n]
@bootstrap
def build2(self, n):
self.visited[n] = True
if self.heavy[n] != -1:
v = self.heavy[n]
self.top[v] = self.top[n]
self.HLD_G.append(v)
yield self.build2(v)
for v, _ in self.G[n]:
if not self.visited[v] and v != self.heavy[n]:
self.top[v] = v
self.HLD_G.append(v)
yield self.build2(v)
yield
def make_tree(self):
for i, n in enumerate(self.HLD_G[:-1]):
for v, w in self.G[n]:
if v == self.parent[n]:
self.node_w[i] = w
break
self.node[n] = i
self.Tree = SegTree(self.node_w, self.segfunc, self.ide_ele)
・HL分解（頂点）
class HLDecomposition:
def __init__(self, N, G, segfunc, ide_ele):
self.N = N
self.G = G
self.segfunc = segfunc
self.ide_ele = ide_ele
self.parent = [-1]*N
self.depth = [0]*N
self.size = [1]*N
self.heavy = [-1]*N
self.visited = [False]*N
self.build1(0)
self.top = [0]*N
self.HLD_G = [0]
self.visited = [False]*N
self.build2(0)
self.HLD_G = self.HLD_G[::-1]
self.node_w = [0]*N
self.node = [N-1]*N
self.make_tree()
def update(self, n, weight):
self.Tree.update(self.node[n], weight)
def query(self, l, r):
sml, smr = self.ide_ele, self.ide_ele
while True:
li, ri = self.node[l], self.node[r]
if self.top[l] == self.top[r]:
if self.depth[l] > self.depth[r]:
sml = self.segfunc(sml, self.Tree.query(li, ri+1))
else:
smr = self.segfunc(self.Tree.query(ri, li+1), smr)
return self.segfunc(sml, smr)
else:
l_top, r_top = self.top[l], self.top[r]
if self.depth[l_top] > self.depth[r_top]:
sml = self.segfunc(sml, self.Tree.query(li, self.node[l_top]+1))
l = self.parent[l_top]
else:
smr = self.segfunc(self.Tree.query(ri, self.node[r_top]+1), smr)
r = self.parent[r_top]
@bootstrap
def build1(self, n):
self.visited[n] = True
for v in self.G[n]:
if not self.visited[v]:
self.parent[v] = n
self.depth[v] = self.depth[n]+1
self.size[n] += yield self.build1(v)
if self.heavy[n] == -1 or self.size[self.heavy[n]] < self.size[v]:
self.heavy[n] = v
yield self.size[n]
@bootstrap
def build2(self, n):
self.visited[n] = True
if self.heavy[n] != -1:
v = self.heavy[n]
self.top[v] = self.top[n]
self.HLD_G.append(v)
yield self.build2(v)
for v in self.G[n]:
if not self.visited[v] and v != self.heavy[n]:
self.top[v] = v
self.HLD_G.append(v)
yield self.build2(v)
yield
def make_tree(self):
for i, n in enumerate(self.HLD_G):
self.node_w[i] = A[n]
self.node[n] = i
self.Tree = SegTree(self.node_w, self.segfunc, self.ide_ele)
・等比数列
def geometric_progression(a, r, n):
# a = 初項 r = 公比 n = 項数
return a*((pow(r, n, MOD)-1)%MOD)%MOD*inverse(1, r-1)%MOD
・ベクトル
def vec(a, b):
return (b[0]-a[0], b[1]-a[1])
・ベクトルの絶対値
def vec2(a):
return (a[0]**2+a[1]**2)**0.5
・内積
def inner_product(v1, v2):
return v1[0]*v2[0]+v1[1]*v2[1]
・外積
def cross_product(v1, v2):
return v1[0]*v2[1]-v1[1]*v2[0]
・∠BACの角度
def angle(bx, by, ax, ay, cx, cy):
ab = vec((ax, ay), (bx, by))
ac = vec((ax, ay), (cx, cy))
top = ab[0]*ac[0]+ab[1]*ac[1]
if cross_product(ab, ac) <= 0:
return degrees(acos(top/(vec2(ab)*vec2(ac))))
else:
return 360-degrees(acos(top/(vec2(ab)*vec2(ac))))
・組み合わせの数
class CP:
def __init__(self, N):
self.fact = [1]*(N+1)
self.fact_inv = [1]*(N+1)
for i in range(2, N+1):
self.fact[i] = self.fact[i-1]*i%MOD
self.fact_inv[N] = pow(self.fact[N], -1, MOD)
for i in reversed(range(1, N)):
self.fact_inv[i] = self.fact_inv[i+1]*(i+1)%MOD
def C(self, N, K):
if N < 0 or K < 0 or N < K:
return 0
return self.fact[N]*self.fact_inv[K]%MOD*self.fact_inv[N-K]%MOD
def P(self, N, K):
if N < 0 or K < 0 or N < K:
return 0
return self.fact[N]*self.fact_inv[N-K]%MOD
def H(self, N, K):
if N < 0 or K < 0:
return 0
if N == K == 0: return 1
return self.C(N+K-1, K)
・Dinic
class Dinic_edge:
def __init__(self, t, cap, rev):
self.t = t
self.cap = cap
self.rev = rev
class Dinic:
def __init__(self, N):
self.N = N
self.G = [[] for _ in range(N)]
def add_edge(self, u, v, cap):
self.G[u].append(Dinic_edge(v, cap, len(self.G[v])))
self.G[v].append(Dinic_edge(u, 0, len(self.G[u])-1))
def bfs(self, s, to):
self.level = [-1]*self.N
que = deque()
que.append(s)
self.level[s] = 0
while que:
n = que.popleft()
for v in self.G[n]:
if v.cap and self.level[v.t] == -1:
self.level[v.t] = self.level[n]+1
que.append(v.t)
return self.level[to] != -1
@bootstrap
def dfs(self, n, to, f):
if n == to:
yield f
for v in self.it[n]:
if v.cap and self.level[n] < self.level[v.t]:
d = yield self.dfs(v.t, to, min(f, v.cap))
if d:
v.cap -= d
self.G[v.t][v.rev].cap += d
yield d
yield 0
def flow(self, s, t):
flow = 0
INF = 10**18
while self.bfs(s, t):
*self.it, = map(iter, self.G)
f = INF
while f:
f = self.dfs(s, t, INF)
flow += f
return flow
・ポラード・ロー素因数分解
def gcd(a, b):
while a:
a, b = b%a, a
return b
def is_prime(n):
if n == 2:
return 1
if n == 1 or n%2 == 0:
return 0
m = n - 1
lsb = m & -m
s = lsb.bit_length()-1
d = m // lsb
test_numbers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
for a in test_numbers:
if a == n:
continue
x = pow(a,d,n)
r = 0
if x == 1:
continue
while x != m:
x = pow(x,2,n)
r += 1
if x == 1 or r == s:
return 0
return 1
def find_prime_factor(n):
if n%2 == 0:
return 2
m = int(n**0.125)+1
for c in range(1,n):
f = lambda a: (pow(a,2,n)+c)%n
y = 0
g = q = r = 1
k = 0
while g == 1:
x = y
while k < 3*r//4:
y = f(y)
k += 1
while k < r and g == 1:
ys = y
for _ in range(min(m, r-k)):
y = f(y)
q = q*abs(x-y)%n
g = gcd(q,n)
k += m
k = r
r *= 2
if g == n:
g = 1
y = ys
while g == 1:
y = f(y)
g = gcd(abs(x-y),n)
if g == n:
continue
if is_prime(g):
return g
elif is_prime(n//g):
return n//g
else:
return find_prime_factor(g)
def factorize(n):
res = []
while not is_prime(n) and n > 1: # nが合成数である間nの素因数の探索を繰り返す
p = find_prime_factor(n)
s = 0
while n%p == 0: # nが素因数pで割れる間割り続け、出力に追加
n //= p
s += 1
res.append((p, s))
if n > 1: # n>1であればnは素数なので出力に追加
res.append((n, 1))
return res
def divisor(n):
ans = [1]
pf = factorize(n)
for p, c in pf:
L = len(ans)
for i in range(L):
v = 1
for _ in range(c):
v *= p
ans.append(ans[i]*v)
return sorted(ans)
・行列の積
def matrix(a, b):
ans = [[0]*len(b[0]) for _ in range(len(a))]
for i in range(len(a)):
for j in range(len(b[0])):
for k in range(len(b)):
ans[i][j] += a[i][k]*b[k][j]%MOD
ans[i][j] %= MOD
return ans
・座標と行列から移動後の座標を求める
def place(a, b):
X = sum(a[0][i]*b[i] for i in range(3))
Y = sum(a[1][i]*b[i] for i in range(3))
return X, Y
・変換行列
def OP(n, p):
# 時計回りに90度回転
if n == 1:
A = [(0, 1, 0), (-1, 0, 0), (0, 0, 1)]
# 反時計回りに90度回転
elif n == 2:
A = [(0, -1, 0), (1, 0, 0), (0, 0, 1)]
# x軸pに対称な位置に移動
elif n == 3:
A = [(-1, 0, 2*p), (0, 1, 0), (0, 0, 1)]
# y軸pに対称な位置に移動
else:
A = [(1, 0, 0), (0, -1, 2*p), (0, 0, 1)]
return A
・WaveletMatrix
from itertools import accumulate
from typing import Optional
class BitVector:
def __init__(self, B: list[int]):
self.B = B
self.acc = list(accumulate(B))
def __len__(self) -> int:
return len(self.B)
def __getitem__(self, i: int) -> int:
return self.B[i]
def rank0(self, i: int) -> int:
if i <= 0:
return 0
i = min(i, len(self))
return i - self.rank1(i)
def rank1(self, i: int) -> int:
if i <= 0:
return 0
i = min(i, len(self))
return self.acc[i - 1]
def rank0_all(self) -> int:
return self.rank0(len(self.B))
def rank1_all(self) -> int:
return self.rank1(len(self.B))
def select0(self, k: int) -> Optional[int]:
if (k <= 0) or (k > self.rank0_all()):
return None
left, right = 0, len(self)
while (right - left) > 1:
mid = (left + right) // 2
if self.rank0(mid) < k:
left = mid
else:
right = mid
return left
def select1(self, k: int) -> Optional[int]:
if (k <= 0) or (k > self.rank1_all()):
return None
left, right = 0, len(self)
while (right - left) > 1:
mid = (left + right) // 2
if self.rank1(mid) < k:
left = mid
else:
right = mid
return left
class WaveletMatrix:
def __init__(self, T: list[int]):
self.bit_size: int = max(T).bit_length() if T else 0
self.wavelet_matrix: list[BitVector] = self._build(T)
def _build(self, T: list[int]) -> list[BitVector]:
wavelet_matrix: list[BitVector] = []
for digit in range(self.bit_size)[::-1]:
zeros = [t for t in T if not self._get_i_bit(t, digit + 1)]
ones = [t for t in T if self._get_i_bit(t, digit + 1)]
T = zeros + ones
wavelet_matrix.append(BitVector([self._get_i_bit(t, digit) for t in T]))
return wavelet_matrix
def __len__(self) -> int:
if len(self.wavelet_matrix) == 0:
return 0
return len(self.wavelet_matrix[0])
def __getitem__(self, i: int) -> int:
return self.access(i)
def _get_i_bit(self, x: int, digit: int) -> int:
return 1 & (x >> digit)
def _next_range(self, B: BitVector, bit: int, left: int, right: int) -> tuple[int, int]:
if bit == 0:
left = B.rank0(left)
right = B.rank0(right)
else:
left = B.rank0_all() + B.rank1(left)
right = B.rank0_all() + B.rank1(right)
return (left, right)
def access(self, i: int) -> int:
x = 0
for digit, B in enumerate(self.wavelet_matrix):
bit = B[i]
x |= bit << (self.bit_size - digit - 1)
if bit == 0:
i = B.rank0(i + 1) - 1
else:
i = B.rank0_all() + B.rank1(i + 1) - 1
return x
# T[0..right)におけるxの出現回数
def rank(self, x: int, right: int) -> int:
return self.rank_range(x, 0, right)
# T[left..right)におけるxの出現回数
def rank_range(self, x: int, left: int, right: int) -> int:
if (left >= right) or (x.bit_length() > self.bit_size) or (x < 0):
return 0
left = max(left, 0)
right = min(right, len(self))
for digit, B in enumerate(self.wavelet_matrix):
x_bit = self._get_i_bit(x, self.bit_size - digit - 1)
left, right = self._next_range(B, x_bit, left, right)
return right - left
# 元の配列Tのk個目のxの出現位置 (index)
def select(self, x: int, k: int) -> Optional[int]:
if not (0 <= x < 1 << self.bit_size):
return None
if k <= 0:
return None
# xが最終的な配列のどの範囲に入るか計算
left, right = 0, len(self)
for digit, B in enumerate(self.wavelet_matrix):
x_bit = self._get_i_bit(x, self.bit_size - digit - 1)
left, right = self._next_range(B, x_bit, left, right)
if left >= right:
return None
# 上記範囲のk番目が, 元の配列で何番目か計算
index = left + k - 1
for digit, B in enumerate(self.wavelet_matrix[::-1]):
if index is None:
return None
x_bit = self._get_i_bit(x, digit)
if x_bit == 0:
index = B.select0(index + 1)
else:
index = B.select1(index - (B.rank0_all() - 1))
return index
# 元の配列T[left..right)の中のk番目に小さい値
def quantile(self, left: int, right: int, k: int) -> Optional[int]:
if (left >= right) or (k <= 0) or (right - left < k):
return None
left = max(left, 0)
right = min(right, len(self))
x = 0
for digit, B in enumerate(self.wavelet_matrix):
num_zeros = B.rank0(right) - B.rank0(left)
# 該当要素が0の中か or 1の中か
bit = 0 if k <= num_zeros else 1
left, right = self._next_range(B, bit, left, right)
if bit == 1:
k -= num_zeros
x |= bit << (self.bit_size - digit - 1)
return x
# T[left..right)の0 <= x < upper となるxの個数
def range_freq_to(self, left: int, right: int, upper: int) -> int:
if (left >= right) or (upper <= 0):
return 0
# 全ての要素が < upper
if upper.bit_length() > self.bit_size:
return right - left
cnt = 0
left = max(left, 0)
right = min(right, len(self))
for digit, B in enumerate(self.wavelet_matrix):
upper_bit = self._get_i_bit(upper, self.bit_size - digit - 1)
if upper_bit == 1:
cnt += B.rank0(right) - B.rank0(left)
left, right = self._next_range(B, upper_bit, left, right)
return cnt
# T[left..right)のlower <= x となるxの個数
def range_freq_from(self, left: int, right: int, lower: int) -> int:
if (left >= right) or (lower > (1 << self.bit_size)):
return 0
left = max(left, 0)
right = min(right, len(self))
return (right - left) - self.range_freq_to(left, right, lower)
# T[left..right)のlower <= x < upper となるxの個数
def range_freq(self, left: int, right: int, lower: int, upper: int) -> int:
if (left >= right) or (lower >= upper) or (lower > (1 << self.bit_size)):
return 0
return self.range_freq_to(left, right, upper) - self.range_freq_to(
left, right, lower
)
# T[left..right)の中で0 <= x < upperを満たす最大のx
def prev_value(self, left: int, right: int, upper: int) -> Optional[int]:
cnt = self.range_freq_to(left, right, upper)
if cnt == 0:
return None
return self.quantile(left, right, cnt)
# T[left..right)の中で, lower <= x を満たす最小のx
def next_value(self, left: int, right: int, lower: int) -> int:
cnt = self.range_freq_from(left, right, lower)
if cnt == 0:
return None
return self.quantile(left, right, right - left - cnt + 1)
・HopcroftKarp
import sys
sys.setrecursionlimit(10**6)
class HopcroftKarp:
def __init__(self, N1, N2):
self.N1 = N1
self.N2 = N2
self.G = [[] for _ in range(self.N1+1)]
self.pair1 = [0]*(self.N1+1)
self.pair2 = [0]*(self.N2+1)
self.matching_size = -1
def add_edge(self, fr, to):
self.G[fr].append(to)
def bfs(self):
que = deque()
for i in range(1, self.N1+1):
if self.pair1[i] == 0:
self.dist[i] = 0
que.append(i)
else:
self.dist[i] = INF
self.dist[0] = INF
while que:
n = que.popleft()
if self.dist[n] < self.dist[0]:
for v in self.G[n]:
if self.dist[self.pair2[v]] == INF:
self.dist[self.pair2[v]] = self.dist[n]+1
que.append(self.pair2[v])
return self.dist[0] != INF
def dfs(self, n):
if n != 0:
for v in self.G[n]:
if self.dist[self.pair2[v]] == self.dist[n]+1:
if self.dfs(self.pair2[v]):
self.pair2[v] = n
self.pair1[n] = v
return True
self.dist[n] = INF
return False
return True
def flow(self):
if self.matching_size != -1:
return self.matching_size
self.dist = [0]*(self.N1+1)
ans = 0
while self.bfs():
for i in range(1, self.N1+1):
if self.pair1[i] == 0 and self.dfs(i):
ans += 1
self.matching_size = ans
return ans
def get_matching(self):
if self.matching_size == -1:
self.flow()
ans = []
for i in range(1, self.N1+1):
if self.pair1[i] != 0:
ans.append((i, self.pair1[i]))
return ans
def minimum_vertex_cover(self):
if self.matching_size == -1:
self.flow()
return self.matching_size
def maximum_independent_set(self):
return self.N1+self.N2-self.minimum_vertex_cover()
def minimum_edge_cover(self):
F = [False]*(self.N1+self.N2+1)
for n in range(1, self.N1+1):
F[n] = True
for v in self.G[n]:
F[self.N1+v] = True
if sum(F) < self.N1+self.N2:
return -1
if self.matching_size == -1:
self.flow()
return self.N1+self.N2-self.matching_size
def preparation(self):
if self.matching_size == -1:
self.flow()
L = self.N1+self.N2
G = [[] for _ in range(L+1)]
for n in range(1, self.N1+1):
for v in self.G[n]:
if self.pair1[n] == v:
G[self.N1+v].append(n)
else:
G[n].append(self.N1+v)
visited = [False]*(L+1)
que = deque()
for i in range(1, self.N1+1):
if self.pair1[i] == 0:
visited[i] = True
que.append(i)
while que:
n = que.popleft()
for v in G[n]:
if not visited[v]:
visited[v] = True
que.append(v)
return visited
def get_minimum_vertex_cover(self):
visited = self.preparation()
ans1 = []
ans2 = []
for i in range(1, self.N1+self.N2+1):
if i <= self.N1 and not visited[i]:
ans1.append(i)
elif self.N1+1 <= i and visited[i]:
ans2.append(i-self.N1)
return ans1, ans2
def get_maximum_independent_set(self):
visited = self.preparation()
ans1 = []
ans2 = []
for i in range(1, self.N1+self.N2+1):
if i <= self.N1 and visited[i]:
ans1.append(i)
elif self.N1+1 <= i and not visited[i]:
ans2.append(i-self.N1)
return ans1, ans2
def get_minimum_edge_cover(self):
cnt = self.minimum_edge_cover()
if cnt == -1:
return None
ans = []
pair = [-1]*(self.N1+self.N2+1)
for n in range(1, self.N1+1):
pair[n] = self.G[n][0]
for v in self.G[n]:
if pair[self.N1+v] == -1:
pair[self.N1+v] = n
for i in range(1, self.N1+self.N2+1):
if i <= self.N1 and self.pair1[i] != 0:
ans.append((i, self.pair1[i]))
elif i <= self.N1 and self.pair1[i] == 0:
ans.append((i, pair[i]))
elif self.N1+1 <= i and self.pair2[i-self.N1] == 0:
ans.append((pair[i], i-self.N1))
return ans
・Suffix Array(SA-IS)
from collections import Counter
# SA-IS (O(nlogn))
# s: 文字列
def sais(s):
uniq = list(set(s))
uniq.sort()
return sais_rec(list(map({e: i+1 for i, e in enumerate(uniq)}.__getitem__, s)), len(uniq))
def sais_rec(lst, num):
L = len(lst)
if L < 2:
return lst + [0]
lst = lst + [0]
L += 1
res = [-1] * L
t = [1] * L
for i in range(L-2, -1, -1):
t[i] = 1 if (lst[i] < lst[i+1] or (lst[i] == lst[i+1] and t[i+1])) else 0
isLMS = [t[i-1] < t[i] for i in range(L)]
LMS = [i for i in range(1, L) if t[i-1] < t[i]]
LMSn = len(LMS)
count = Counter(lst)
tmp = 0
cstart = [0]*(num+1)
cend = [0]*(num+1)
for key in range(num+1):
cstart[key] = tmp
cend[key] = tmp = tmp + count[key]
cc_it = [iter(range(e-1, s-1, -1)) for s, e in zip(cstart, cend)]
for e in reversed(LMS):
res[next(cc_it[lst[e]])] = e
cs_it = [iter(range(s, e)) for s, e in zip(cstart, cend)]
ce_it = [iter(range(e-1, s-1, -1)) for s, e in zip(cstart, cend)]
for e in res:
if e > 0 and not t[e-1]:
res[next(cs_it[lst[e-1]])] = e-1
for e in reversed(res):
if e > 0 and t[e-1]:
res[next(ce_it[lst[e-1]])] = e-1
name = 0; prev = -1
pLMS = {}
for e in res:
if isLMS[e]:
if prev == -1 or lst[e] != lst[prev]:
name += 1; prev = e
else:
for i in range(1, L):
if lst[e+i] != lst[prev+i]:
name += 1; prev = e
break
if isLMS[e+i] or isLMS[prev+i]:
break
pLMS[e] = name-1
if name < LMSn:
sublst = [pLMS[e] for e in LMS if e < L-1]
ret = sais_rec(sublst, name-1)
LMS = list(map(LMS.__getitem__, reversed(ret)))
else:
LMS = [e for e in reversed(res) if isLMS[e]]
res = [-1] * L
cc_it = [iter(range(e-1, s-1, -1)) for s, e in zip(cstart, cend)]
for e in LMS:
res[next(cc_it[lst[e]])] = e
cs_it = [iter(range(s, e)) for s, e in zip(cstart, cend)]
ce_it = [iter(range(e-1, s-1, -1)) for s, e in zip(cstart, cend)]
for e in res:
if e > 0 and not t[e-1]:
res[next(cs_it[lst[e-1]])] = e-1
for e in reversed(res):
if e > 0 and t[e-1]:
res[next(ce_it[lst[e-1]])] = e-1
return res
# Longest Common Prefix
# (文字列s, 文字列長n, Suffix Array)を引数として与える
def LCP(s, n, sa):
lcp = [-1]*(n+1)
rank = [0]*(n+1)
for i in range(n+1): rank[sa[i]] = i
h = 0
lcp[0] = 0
for i in range(n):
j = sa[rank[i] - 1]
if h > 0: h -= 1
while j+h < n and i+h < n and s[j+h]==s[i+h]:
h += 1
lcp[rank[i] - 1] = h
return lcp
・最小費用流
# https://atcoder.jp/contests/practice2/submissions/33588016
from heapq import heappush, heappop
class MinCostFlow:
"""
https://github.com/atcoder/ac-library/blob/master/atcoder/internal_csr.hpp
https://github.com/atcoder/ac-library/blob/master/atcoder/mincostflow.hpp
https://github.com/atcoder/ac-library/blob/master/document_en/mincostflow.md
https://github.com/atcoder/ac-library/blob/master/document_ja/mincostflow.md
"""
def __init__(self, n):
self.n = n
self._edges = []
def add_edge(self, fr, to, cap, cost):
assert 0 <= fr < self.n
assert 0 <= to < self.n
assert 0 <= cap
assert 0 <= cost
self._edges.append(self.edge(fr, to, cap, cost))
return len(self._edges) - 1
class edge:
def __init__(self, fr, to, cap, cost):
self.fr = fr
self.to = to
self.cap = cap
self.flow = 0
self.cost = cost
def get_edge(self, i):
assert 0 <= i < len(self._edges)
return self._edges[i]
def edges(self):
return self._edges
def flow(self, s, t, flow_limit=1<<60):
return self.slope(s, t, flow_limit)[-1]
def __csr(self, edges):
# Compressed Sparse Row
self.start = [0] * (self.n + 1)
for fr, _ in edges:
self.start[fr + 1] += 1
for i in range(self.n):
self.start[i + 1] += self.start[i]
counter = self.start.copy()
self.elist = [0] * len(edges)
for fr, e in edges:
self.elist[counter[fr]] = e
counter[fr] += 1
class _edge:
def __init__(self, to, rev, cap, cost):
self.to = to
self.rev = rev
self.cap = cap
self.cost = cost
def __g(self):
degree = [0] * self.n
redge_idx = [0] * self.m
elist = [(0, None)] * (2 * self.m)
now_elist = 0
for i in range(self.m):
e = self._edges[i]
self.edge_idx[i] = degree[e.fr]
degree[e.fr] += 1
redge_idx[i] = degree[e.to]
degree[e.to] += 1
elist[now_elist] = (e.fr, self._edge(e.to, -1, e.cap - e.flow, e.cost))
now_elist += 1
elist[now_elist] = (e.to, self._edge(e.fr, -1, e.flow, -e.cost))
now_elist += 1
self.__csr(elist)
for i in range(self.m):
e = self._edges[i]
self.edge_idx[i] += self.start[e.fr]
redge_idx[i] += self.start[e.to]
self.elist[self.edge_idx[i]].rev = redge_idx[i]
self.elist[redge_idx[i]].rev = self.edge_idx[i]
def slope(self, s, t, flow_limit=1<<60):
assert 0 <= s < self.n
assert 0 <= t < self.n
assert s != t
self.m = len(self._edges)
self.edge_idx = [0] * self.m
self.__g()
result = self.__slope(s, t, flow_limit)
for i in range(self.m):
e = self.elist[self.edge_idx[i]]
self._edges[i].flow = self._edges[i].cap - e.cap
return result
def __dual_ref(self, s, t):
log = self.n.bit_length()
mask = (1<<log) - 1
dist = [1<<60] * self.n
vis = [0] * self.n
que_min = []
que = []
dist[s] = 0
que_min.append(s)
while que_min or que:
if que_min:
v = que_min.pop()
else:
v = heappop(que) & mask
if vis[v]:
continue
vis[v] = 1
if v == t:
break
# dist[v] = shortest(s, v) + dual[s] - dual[v]
# dist[v] >= 0 (all reduced cost are positive)
# dist[v] <= (n-1)C
dual_v = self.dual[v]
dist_v = dist[v]
for i in range(self.start[v], self.start[v+1]):
e = self.elist[i]
if not e.cap:
continue
# |-dual[e.to] + dual[v]| <= (n-1)C
# cost <= C - -(n-1)C + 0 = nC
cost = e.cost - self.dual[e.to] + dual_v
if dist[e.to] - dist_v > cost:
dist_to = dist_v + cost
dist[e.to] = dist_to
self.prev_e[e.to] = e.rev
if dist_to == dist_v:
que_min.append(e.to)
else:
heappush(que, dist_to<<log | e.to)
if not vis[t]:
return False
for v in range(self.n):
if not vis[v]:
continue
# dual[v]
# = dual[v] - dist[t] + dist[v]
# = dual[v] - (shortest(s, t) + dual[s] - dual[t]) + (shortest(s, v) + dual[s] - dual[v])
# = - shortest(s, t) + dual[t] + shortest(s, v)
# = shortest(s, v) - shortest(s, t)
# >= 0 - (n-1)C
self.dual[v] -= dist[t] - dist[v]
return True
def __slope(self, s, t, flow_limit):
# variants (C = maxcost):
# -(n-1)C <= dual[s] <= dual[i] <= dual[t] = 0
# reduced cost (= e.cost + dual[e.from] - dual[e.to]) >= 0 for all edge
self.dual = [0] * self.n
self.prev_e = [0] * self.n
flow = 0
cost = 0
prev_cost_per_flow = -1
result = [(0, 0)]
while flow < flow_limit:
if not self.__dual_ref(s, t):
break
c = flow_limit - flow
v = t
while v != s:
c = min(c, self.elist[self.elist[self.prev_e[v]].rev].cap)
v = self.elist[self.prev_e[v]].to
v = t
while v != s:
e = self.elist[self.prev_e[v]]
e.cap += c
self.elist[e.rev].cap -= c
v = self.elist[self.prev_e[v]].to
d = -self.dual[s]
flow += c
cost += c * d
if prev_cost_per_flow == d:
result.pop()
result.append((flow, cost))
prev_cost_per_flow = d
return result
・エラトステネスのふるいを用いた高速素因数分解と高速約数列挙
class Eratosthenes:
def __init__(self, n):
self.isPrime = [True]*(n+1)
self.minfactor = [-1]*(n+1)
self.isPrime[0], self.isPrime[1] = False, False
self.minfactor[1] = 1
for i in range(2, n+1):
if self.isPrime[i]:
self.minfactor[i] = i
for j in range(i*i, n+1, i):
self.isPrime[j] = False
if self.minfactor[j] == -1:
self.minfactor[j] = i
def factorize(self, n):
factor = []
while n > 1:
p = self.minfactor[n]
cnt = 0
while self.minfactor[n] == p:
n //= p
cnt += 1
factor.append((p, cnt))
return factor
def divisor(self, n):
ans = [1]
pf = self.factorize(n)
for p, c in pf:
L = len(ans)
for i in range(L):
v = 1
for _ in range(c):
v *= p
ans.append(ans[i]*v)
return ans
・高速ゼータ変換、高速メビウス変換
def Eratosthenes(n):
isPrime = [True]*(n+1)
isPrime[0], isPrime[1] = False, False
for i in range(2, n+1):
if isPrime[i]:
for j in range(i*i, n+1, i):
isPrime[j] = False
return isPrime
def fast_zeta(F):
isPrime = Eratosthenes(len(F))
print(F)
for i in range(2, len(F)):
if isPrime[i]:
for j in range((len(F)-1)//i, 0, -1):
F[j] += F[j*i]
print(F)
def fast_mobius(F):
isPrime = Eratosthenes(len(F))
for i in range(2, len(F)):
if isPrime[i]:
for j in range(1, (len(F)-1)//i+1):
F[j] -= F[j*i]
・メビウス関数値の列挙
class Eratosthenes:
def __init__(self, n):
self.isPrime = [True]*(n+1)
self.isPrime[0], self.isPrime[1] = False, False
self.mobius = [1]*(n+1)
for i in range(2, n+1):
if self.isPrime[i]:
self.mobius[i] = -1
for j in range(i*2, n+1, i):
self.isPrime[j] = False
if j//i%i == 0:
self.mobius[j] = 0
else:
self.mobius[j] *= -1
・オイラーのφ関数
def Euler(n):
div = divisor(n)
ans = 0
E = Eratosthenes(n)
for d in div:
ans += n//d*E.mobius[d]
return ans
・座標圧縮
def compress(A):
S = sorted(set(A))
D = dict()
for i in range(len(S)):
D[S[i]] = i
return D
・マージソートツリー（X以下や以上の個数）
class MergeSortTree:
def __init__(self, init_val):
n = len(init_val)
self.n = n
self.num = 1<<(n-1).bit_length()
self.tree = [[] for _ in range(self.num*2)]
for i in range(n):
self.tree[self.num+i].append(init_val[i])
for i in range(self.num-1, 0, -1):
left, right = 2*i, 2*i+1
idxL, idxR = 0, 0
while idxL < len(self.tree[left]) or idxR < len(self.tree[right]):
if idxL == len(self.tree[left]):
self.tree[i].append(self.tree[right][idxR])
idxR += 1
elif idxR == len(self.tree[right]):
self.tree[i].append(self.tree[left][idxL])
idxL += 1
else:
if self.tree[left][idxL] <= self.tree[right][idxR]:
self.tree[i].append(self.tree[left][idxL])
idxL += 1
else:
self.tree[i].append(self.tree[right][idxR])
idxR += 1
# bisectのleftとrightを書き換えれば、Xより小さい数 or Xより大きい数 のクエリにも対応可能
# sum(A[i] <= X for i in range(l, r))
def query1(self, l, r, X):
ans = 0
l += self.num
r += self.num
while l < r:
if l & 1:
ans += bisect_right(self.tree[l], X)
l += 1
if r & 1:
ans += bisect_right(self.tree[r-1], X)
l >>= 1
r >>= 1
return ans
# sum(A[i] >= X for i in range(l, r))
def query2(self, l, r, X):
ans = 0
l += self.num
r += self.num
while l < r:
if l & 1:
ans += len(self.tree[l])-bisect_left(self.tree[l], X)
l += 1
if r & 1:
ans += len(self.tree[r-1])-bisect_left(self.tree[r-1], X)
l >>= 1
r >>= 1
return ans
# sum(leftX <= A[i] <= rightX for i in range(l, r))
def query3(self, l, r, leftX, rightX):
ans = r-l
l += self.num
r += self.num
while l < r:
if l & 1:
ans -= bisect_left(self.tree[l], leftX)
ans -= len(self.tree[l])-bisect_right(self.tree[l], rightX)
l += 1
if r & 1:
ans -= bisect_left(self.tree[r-1], leftX)
ans -= len(self.tree[r-1])-bisect_right(self.tree[r-1], rightX)
l >>= 1
r >>= 1
return ans
・マージソートツリー（X以下や以上の個数、総和）
class MergeSortTree:
def __init__(self, init_val):
n = len(init_val)
self.n = n
self.num = 1<<(n-1).bit_length()
self.tree = [[] for _ in range(self.num*2)]
self.cum = [[0] for _ in range(self.num*2)]
for i in range(n):
self.tree[self.num+i].append(init_val[i])
for i in range(self.num-1, 0, -1):
left, right = 2*i, 2*i+1
idxL, idxR = 0, 0
while idxL < len(self.tree[left]) or idxR < len(self.tree[right]):
if idxL == len(self.tree[left]):
self.tree[i].append(self.tree[right][idxR])
idxR += 1
elif idxR == len(self.tree[right]):
self.tree[i].append(self.tree[left][idxL])
idxL += 1
else:
if self.tree[left][idxL] <= self.tree[right][idxR]:
self.tree[i].append(self.tree[left][idxL])
idxL += 1
else:
self.tree[i].append(self.tree[right][idxR])
idxR += 1
for i in range(1, self.num*2):
for j in range(len(self.tree[i])):
self.cum[i].append(self.cum[i][-1]+self.tree[i][j])
# bisectのleftとrightを書き換えれば、Xより小さい数 or Xより大きい数 のクエリにも対応可能
# sum(A[i] <= X for i in range(l, r))
def query1(self, l, r, X):
ans = 0
l += self.num
r += self.num
while l < r:
if l & 1:
ans += bisect_right(self.tree[l], X)
l += 1
if r & 1:
ans += bisect_right(self.tree[r-1], X)
l >>= 1
r >>= 1
return ans
# sum(A[i] >= X for i in range(l, r))
def query2(self, l, r, X):
ans = 0
l += self.num
r += self.num
while l < r:
if l & 1:
ans += len(self.tree[l])-bisect_left(self.tree[l], X)
l += 1
if r & 1:
ans += len(self.tree[r-1])-bisect_left(self.tree[r-1], X)
l >>= 1
r >>= 1
return ans
# sum(leftX <= A[i] <= rightX for i in range(l, r))
def query3(self, l, r, leftX, rightX):
ans = r-l
l += self.num
r += self.num
while l < r:
if l & 1:
ans -= bisect_left(self.tree[l], leftX)
ans -= len(self.tree[l])-bisect_right(self.tree[l], rightX)
l += 1
if r & 1:
ans -= bisect_left(self.tree[r-1], leftX)
ans -= len(self.tree[r-1])-bisect_right(self.tree[r-1], rightX)
l >>= 1
r >>= 1
return ans
# sum(A[i] for i in range(l, r) if A[i] <= X)
def query4(self, l, r, X):
ans = 0
l += self.num
r += self.num
while l < r:
if l & 1:
b = bisect_right(self.tree[l], X)
ans += self.cum[l][b]
l += 1
if r & 1:
b = bisect_right(self.tree[r-1], X)
ans += self.cum[r-1][b]
l >>= 1
r >>= 1
return ans
# sum(A[i] for i in range(l, r) if A[i] >= X)
def query5(self, l, r, X):
ans = 0
l += self.num
r += self.num
while l < r:
if l & 1:
b = bisect_left(self.tree[l], X)
ans += self.cum[l][-1]-self.cum[l][b]
l += 1
if r & 1:
b = bisect_left(self.tree[r-1], X)
ans += self.cum[r-1][-1]-self.cum[r-1][b]
l >>= 1
r >>= 1
return ans
# sum(A[i] for i in range(l, r) if leftX <= A[i] <= rightX)
def query6(self, l, r, leftX, rightX):
ans = 0
l += self.num
r += self.num
while l < r:
if l & 1:
left = bisect_left(self.tree[l], leftX)
right = bisect_right(self.tree[l], rightX)
ans += self.cum[l][right]-self.cum[l][left]
l += 1
if r & 1:
left = bisect_left(self.tree[r-1], leftX)
right = bisect_right(self.tree[r-1], rightX)
ans += self.cum[r-1][right]-self.cum[r-1][left]
l >>= 1
r >>= 1
return ans
・行列の積
def matrix(a, b):
ans = [[0]*len(b[0]) for _ in range(len(a))]
for i in range(len(a)):
for j in range(len(b[0])):
ans[i][j] = sum(a[i][k]*b[k][j] for k in range(len(b)))
return ans
・中国剰余定理
def CRT(B, M):
r, m = 0, 1
for i in range(len(B)):
d, x, y = extended_euclid(m, M[i])
if (B[i]-r)%d != 0:
return 0, -1
tmp = (B[i]-r)//d*x%(M[i]//d)
r += m*tmp
m *= M[i]//d
return r, m
・BIT
class BIT:
def __init__(self, A):
self.size = len(A)
self.bit = [0]*(len(A)+1)
for i in range(len(A)):
self.add(i, A[i])
def sum(self, i):
i += 1
ans = 0
while i > 0:
ans += self.bit[i]
i -= -i&i
return ans
def query(self, l, r):
if l == 0:
return self.sum(r-1)
else:
return self.sum(r-1)-self.sum(l-1)
def add(self, i, x):
i += 1
while i <= self.size:
self.bit[i] += x
i += -i&i
・線分の交差判定
def judge(ax, ay, bx, by, cx, cy, dx, dy):
s = (ax-bx)*(cy-ay)-(ay-by)*(cx-ax)
t = (ax-bx)*(dy-ay)-(ay-by)*(dx-ax)
if s*t > 0:
return False
s = (cx-dx)*(ay-cy)-(cy-dy)*(ax-cx)
t = (cx-dx)*(by-cy)-(cy-dy)*(bx-cx)
if s*t > 0:
return False
return True
・二次元累積和
class cum2:
def __init__(self, A):
self.cum = [[0]*(len(A[0])+1) for _ in range(len(A)+1)]
for i in range(len(A)):
for j in range(len(A[0])):
self.cum[i+1][j+1] = A[i][j]
for i in range(1, len(A)+1):
for j in range(2, len(A[0])+1):
self.cum[i][j] += self.cum[i][j-1]
for i in range(2, len(A)+1):
for j in range(1, len(A[0])+1):
self.cum[i][j] += self.cum[i-1][j]
def query(self, lh, rh, lw, rw):
return self.cum[rh+1][rw+1]+self.cum[lh][lw]-self.cum[rh+1][lw]-self.cum[lh][rw+1]
・三次元累積和
class cum3:
def __init__(self, A):
self.cum = [[[0]*(len(A[0][0])+1) for _ in range(len(A[0])+1)] for _ in range(len(A)+1)]
for i in range(len(A)):
for j in range(len(A[0])):
for k in range(len(A[0][0])):
self.cum[i+1][j+1][k+1] = A[i][j][k]
for i in range(1, len(A)+1):
for j in range(1, len(A[0])+1):
for k in range(2, len(A[0][0])+1):
self.cum[i][j][k] += self.cum[i][j][k-1]
for i in range(1, len(A)+1):
for j in range(2, len(A[0])+1):
for k in range(1, len(A[0][0])+1):
self.cum[i][j][k] += self.cum[i][j-1][k]
for i in range(2, len(A)+1):
for j in range(1, len(A[0])+1):
for k in range(1, len(A[0][0])+1):
self.cum[i][j][k] += self.cum[i-1][j][k]
def query(self, lh, rh, ld, rd, lw, rw):
return (self.cum[rh+1][rd+1][rw+1]+self.cum[rh+1][ld][lw]-self.cum[rh+1][rd+1][lw]-self.cum[rh+1][ld][rw+1]
-self.cum[lh][rd+1][rw+1]-self.cum[lh][ld][lw]+self.cum[lh][rd+1][lw]+self.cum[lh][ld][rw+1])
・LowLink
class LowLink:
def __init__(self, N):
self.N = N
self.M = 0
self.G = [[] for _ in range(N)]
def add_edge(self, u, v):
self.G[u].append((v, self.M))
self.G[v].append((u, self.M))
self.M += 1
@bootstrap
def dfs(self, n, parent):
self.visited[n] = True
self.ord[n], self.low[n] = self.cnt, self.cnt
self.cnt += 1
is_ap = False
child = 0
for v, idx in self.G[n]:
if not self.visited[v]:
child += 1
yield self.dfs(v, idx)
self.low[n] = min(self.low[n], self.low[v])
if parent != -1 and self.ord[n] <= self.low[v]:
is_ap = True
if self.ord[n] < self.low[v]:
self.bridge.append(idx)
elif idx != parent:
self.low[n] = min(self.low[n], self.ord[v])
if parent == -1 and 2 <= child:
is_ap = True
if is_ap:
self.articulation_points.append(n)
yield
def find(self):
self.ord = [-1]*self.N
self.low = [-1]*self.N
self.visited = [False]*self.N
self.cnt = 0
self.articulation_points = []
self.bridge = []
for i in range(self.N):
if not self.visited[i]:
self.dfs(i, -1)
return sorted(self.articulation_points), sorted(self.bridge)
・Trie木
class Trie:
def __init__(self, N, type):
self.tree = [[-1]*26 for _ in range(N+1)]
self.arrive = [0]*(N+1)
self.last = [0]*(N+1)
self.nex = 1
if type == 0:
self.base = ord("a")
else:
self.base = ord("A")
def insert(self, S):
now = 0
self.arrive[now] += 1
for s in S:
if self.tree[now][ord(s)-self.base] == -1:
self.tree[now][ord(s)-self.base] = self.nex
now = self.nex
self.nex += 1
else:
now = self.tree[now][ord(s)-self.base]
self.arrive[now] += 1
self.last[now] += 1
def search(self, S):
now = 0
for s in S:
if self.tree[now][ord(s)-self.base] == -1:
return 0
now = self.tree[now][ord(s)-self.base]
return self.last[now]
def start_with(self, S):
now = 0
for s in S:
if self.tree[now][ord(s)-self.base] == -1:
return 0
now = self.tree[now][ord(s)-self.base]
return self.arrive[now]
def count(self):
return self.arrive[0]
・分割
# dp[i][j] jをi以下の数字で分割する個数
def division1(n):
dp = [[0]*(n+1) for _ in range(n+1)]
dp[0][0] = 1
for i in range(1, n+1):
for j in range(n+1):
if j-i >= 0:
dp[i][j] = (dp[i-1][j]+dp[i][j-i])%MOD
else:
dp[i][j] = dp[i-1][j]
return dp
# dp[i][j] iを長さがjの数字に分割する個数
def division2(n):
dp = [[0]*(n+1) for _ in range(n+1)]
dp[0][0] = 1
for i in range(1, n+1):
for j in range(1, n+1):
if i-j >= 0:
dp[i][j] = (dp[i-1][j-1]+dp[i-j][j])%MOD
else:
dp[i][j] = dp[i-1][j-1]
return dp
# dp[i][j] iを長さがj以下の数字に分割する個数
def division3(n):
dp = [[0]*(n+1) for _ in range(n+1)]
dp[0][0] = 1
for i in range(1, n+1):
for j in range(1, n+1):
if i-j >= 0:
dp[i][j] = (dp[i][j-1]+dp[i-j][j])%MOD
else:
dp[i][j] = dp[i][j-1]
return dp
・SortedSet(tatyam)
# https://github.com/tatyam-prime/SortedSet/blob/main/SortedSet.py
import math
from bisect import bisect_left, bisect_right
from typing import Generic, Iterable, Iterator, List, Tuple, TypeVar, Optional
T = TypeVar('T')
class SortedSet(Generic[T]):
BUCKET_RATIO = 16
SPLIT_RATIO = 24
def __init__(self, a: Iterable[T] = []) -> None:
"Make a new SortedSet from iterable. / O(N) if sorted and unique / O(N log N)"
a = list(a)
n = len(a)
if any(a[i] > a[i + 1] for i in range(n - 1)):
a.sort()
if any(a[i] >= a[i + 1] for i in range(n - 1)):
a, b = [], a
for x in b:
if not a or a[-1] != x:
a.append(x)
n = self.size = len(a)
num_bucket = int(math.ceil(math.sqrt(n / self.BUCKET_RATIO)))
self.a = [a[n * i // num_bucket : n * (i + 1) // num_bucket] for i in range(num_bucket)]
def __iter__(self) -> Iterator[T]:
for i in self.a:
for j in i: yield j
def __reversed__(self) -> Iterator[T]:
for i in reversed(self.a):
for j in reversed(i): yield j
def __eq__(self, other) -> bool:
return list(self) == list(other)
def __len__(self) -> int:
return self.size
def __repr__(self) -> str:
return "SortedSet" + str(self.a)
def __str__(self) -> str:
s = str(list(self))
return "{" + s[1 : len(s) - 1] + "}"
def _position(self, x: T) -> Tuple[List[T], int, int]:
"return the bucket, index of the bucket and position in which x should be. self must not be empty."
for i, a in enumerate(self.a):
if x <= a[-1]: break
return (a, i, bisect_left(a, x))
def __contains__(self, x: T) -> bool:
if self.size == 0: return False
a, _, i = self._position(x)
return i != len(a) and a[i] == x
def add(self, x: T) -> bool:
"Add an element and return True if added. / O(√N)"
if self.size == 0:
self.a = [[x]]
self.size = 1
return True
a, b, i = self._position(x)
if i != len(a) and a[i] == x: return False
a.insert(i, x)
self.size += 1
if len(a) > len(self.a) * self.SPLIT_RATIO:
mid = len(a) >> 1
self.a[b:b+1] = [a[:mid], a[mid:]]
return True
def _pop(self, a: List[T], b: int, i: int) -> T:
ans = a.pop(i)
self.size -= 1
if not a: del self.a[b]
return ans
def discard(self, x: T) -> bool:
"Remove an element and return True if removed. / O(√N)"
if self.size == 0: return False
a, b, i = self._position(x)
if i == len(a) or a[i] != x: return False
self._pop(a, b, i)
return True
def lt(self, x: T) -> Optional[T]:
"Find the largest element < x, or None if it doesn't exist."
for a in reversed(self.a):
if a[0] < x:
return a[bisect_left(a, x) - 1]
def le(self, x: T) -> Optional[T]:
"Find the largest element <= x, or None if it doesn't exist."
for a in reversed(self.a):
if a[0] <= x:
return a[bisect_right(a, x) - 1]
def gt(self, x: T) -> Optional[T]:
"Find the smallest element > x, or None if it doesn't exist."
for a in self.a:
if a[-1] > x:
return a[bisect_right(a, x)]
def ge(self, x: T) -> Optional[T]:
"Find the smallest element >= x, or None if it doesn't exist."
for a in self.a:
if a[-1] >= x:
return a[bisect_left(a, x)]
def __getitem__(self, i: int) -> T:
"Return the i-th element."
if i < 0:
for a in reversed(self.a):
i += len(a)
if i >= 0: return a[i]
else:
for a in self.a:
if i < len(a): return a[i]
i -= len(a)
raise IndexError
def pop(self, i: int = -1) -> T:
"Pop and return the i-th element."
if i < 0:
for b, a in enumerate(reversed(self.a)):
i += len(a)
if i >= 0: return self._pop(a, ~b, i)
else:
for b, a in enumerate(self.a):
if i < len(a): return self._pop(a, b, i)
i -= len(a)
raise IndexError
def index(self, x: T) -> int:
"Count the number of elements < x."
ans = 0
for a in self.a:
if a[-1] >= x:
return ans + bisect_left(a, x)
ans += len(a)
return ans
def index_right(self, x: T) -> int:
"Count the number of elements <= x."
ans = 0
for a in self.a:
if a[-1] > x:
return ans + bisect_right(a, x)
ans += len(a)
return ans
・SortedMultiSet(tatyam)
# https://github.com/tatyam-prime/SortedSet/blob/main/SortedMultiset.py
import math
from bisect import bisect_left, bisect_right
from typing import Generic, Iterable, Iterator, List, Tuple, TypeVar, Optional
T = TypeVar('T')
class SortedMultiset(Generic[T]):
BUCKET_RATIO = 16
SPLIT_RATIO = 24
def __init__(self, a: Iterable[T] = []) -> None:
"Make a new SortedMultiset from iterable. / O(N) if sorted / O(N log N)"
a = list(a)
n = self.size = len(a)
if any(a[i] > a[i + 1] for i in range(n - 1)):
a.sort()
num_bucket = int(math.ceil(math.sqrt(n / self.BUCKET_RATIO)))
self.a = [a[n * i // num_bucket : n * (i + 1) // num_bucket] for i in range(num_bucket)]
def __iter__(self) -> Iterator[T]:
for i in self.a:
for j in i: yield j
def __reversed__(self) -> Iterator[T]:
for i in reversed(self.a):
for j in reversed(i): yield j
def __eq__(self, other) -> bool:
return list(self) == list(other)
def __len__(self) -> int:
return self.size
def __repr__(self) -> str:
return "SortedMultiset" + str(self.a)
def __str__(self) -> str:
s = str(list(self))
return "{" + s[1 : len(s) - 1] + "}"
def _position(self, x: T) -> Tuple[List[T], int, int]:
"return the bucket, index of the bucket and position in which x should be. self must not be empty."
for i, a in enumerate(self.a):
if x <= a[-1]: break
return (a, i, bisect_left(a, x))
def __contains__(self, x: T) -> bool:
if self.size == 0: return False
a, _, i = self._position(x)
return i != len(a) and a[i] == x
def count(self, x: T) -> int:
"Count the number of x."
return self.index_right(x) - self.index(x)
def add(self, x: T) -> None:
"Add an element. / O(√N)"
if self.size == 0:
self.a = [[x]]
self.size = 1
return
a, b, i = self._position(x)
a.insert(i, x)
self.size += 1
if len(a) > len(self.a) * self.SPLIT_RATIO:
mid = len(a) >> 1
self.a[b:b+1] = [a[:mid], a[mid:]]
def _pop(self, a: List[T], b: int, i: int) -> T:
ans = a.pop(i)
self.size -= 1
if not a: del self.a[b]
return ans
def discard(self, x: T) -> bool:
"Remove an element and return True if removed. / O(√N)"
if self.size == 0: return False
a, b, i = self._position(x)
if i == len(a) or a[i] != x: return False
self._pop(a, b, i)
return True
def lt(self, x: T) -> Optional[T]:
"Find the largest element < x, or None if it doesn't exist."
for a in reversed(self.a):
if a[0] < x:
return a[bisect_left(a, x) - 1]
def le(self, x: T) -> Optional[T]:
"Find the largest element <= x, or None if it doesn't exist."
for a in reversed(self.a):
if a[0] <= x:
return a[bisect_right(a, x) - 1]
def gt(self, x: T) -> Optional[T]:
"Find the smallest element > x, or None if it doesn't exist."
for a in self.a:
if a[-1] > x:
return a[bisect_right(a, x)]
def ge(self, x: T) -> Optional[T]:
"Find the smallest element >= x, or None if it doesn't exist."
for a in self.a:
if a[-1] >= x:
return a[bisect_left(a, x)]
def __getitem__(self, i: int) -> T:
"Return the i-th element."
if i < 0:
for a in reversed(self.a):
i += len(a)
if i >= 0: return a[i]
else:
for a in self.a:
if i < len(a): return a[i]
i -= len(a)
raise IndexError
def pop(self, i: int = -1) -> T:
"Pop and return the i-th element."
if i < 0:
for b, a in enumerate(reversed(self.a)):
i += len(a)
if i >= 0: return self._pop(a, ~b, i)
else:
for b, a in enumerate(self.a):
if i < len(a): return self._pop(a, b, i)
i -= len(a)
raise IndexError
def index(self, x: T) -> int:
"Count the number of elements < x."
ans = 0
for a in self.a:
if a[-1] >= x:
return ans + bisect_left(a, x)
ans += len(a)
return ans
def index_right(self, x: T) -> int:
"Count the number of elements <= x."
ans = 0
for a in self.a:
if a[-1] > x:
return ans + bisect_right(a, x)
ans += len(a)
return ans
・区間更新 区間和取得
class Node:
def __init__(self, value, size):
self.value = value
self.size = size
def op(left, right):
return Node(left.value+right.value, left.size+right.size)
def mapping(top, bottom):
if top != INF:
return Node(top*bottom.size, bottom.size)
else:
return bottom
def composition(top, bottom):
if top != INF:
return top
else:
return bottom
e = Node(0, 0)
ID = INF
・木の重心
@bootstrap
def dfs(n, pre):
cnt = 1
MAX = -(10**18)
for i, v in enumerate(G[n]):
if v != pre:
c = yield dfs(v, n)
cnt += c
if MAX < c:
MAX = c
maxidx[n] = i
size[n] = cnt
yield size[n]
size = [-1]*N
maxidx = [-1]*N
dfs(0, -1)
@bootstrap
def dfs2(n):
if size[G[n][maxidx[n]]] > N//2:
yield (yield dfs2(G[n][maxidx[n]]))
yield n
center = dfs2(0)
・3点を結ぶ三角形の面積
def area(x1, y1, x2, y2, x3, y3):
return abs((x1-x3)*(y2-y3)-(x2-x3)*(y1-y3))/2
・ChatGPT用
The following code is what I wrote to solve a problem in an AtCoder contest. When using generative AI to translate programming languages during an ongoing AtCoder contest, there are the following restrictions: "It is absolutely necessary to include the original code at the beginning of the submission as a comment or similar." "Only translations that do not alter the algorithm are permitted. In particular, any changes that would affect the time complexity are strictly prohibited." For any parts that cannot be directly translated, please mark them as "FAILED" and leave them unconverted. Following these strict AtCoder rules, please translate the following code from Python to C++.
・文字と数字の変換
def code(s):
return ord(s)-ord("a")
def codeR(n):
return chr(ord("a")+n)
・組み合わせの数（k == 2 or k == 3）
def nC2(n):
return n*(n-1)//2
def nC3(n):
return n*(n-1)*(n-2)//6
・無限等比級数の和
def infinite(a, r):
# a = 初項 r = 公比
return inverse(a, 1-r)
・UnionFind（値を保持）
class UnionFind:
def __init__(self, n, A):
self.n = n
self.parent_size = [-1]*n
self.A = A[:]
def leader(self, a):
if self.parent_size[a] < 0:
return a
self.parent_size[a] = self.leader(self.parent_size[a])
return self.parent_size[a]
def merge(self, a, b):
x, y = self.leader(a), self.leader(b)
if x == y:
return
a = self.A[x]
if abs(self.parent_size[x]) < abs(self.parent_size[y]):
x, y = y, x
self.parent_size[x] += self.parent_size[y]
self.parent_size[y] = x
self.A[x] = a
return
def __getitem__(self, n):
return self.A[self.leader(n)]
def update(self, n, a):
self.A[self.leader(n)] = a
def same(self, a, b):
return self.leader(a) == self.leader(b)
def size(self, a):
return abs(self.parent_size[self.leader(a)])
def groups(self):
result = [[] for _ in range(self.n)]
for i in range(self.n):
result[self.leader(i)].append(i)
return [r for r in result if r != []]
・UnionFind（値を演算）
def op(x, y):
return
class UnionFind:
def __init__(self, n, A, op):
self.n = n
self.parent_size = [-1]*n
self.A = A[:]
self.op = op
def leader(self, a):
if self.parent_size[a] < 0:
return a
self.parent_size[a] = self.leader(self.parent_size[a])
return self.parent_size[a]
def merge(self, a, b):
x, y = self.leader(a), self.leader(b)
if x == y:
return
l, r = self.A[x], self.A[y]
if abs(self.parent_size[x]) < abs(self.parent_size[y]):
x, y = y, x
self.parent_size[x] += self.parent_size[y]
self.parent_size[y] = x
self.A[x] = self.op(l, r)
return
def __getitem__(self, n):
return self.A[self.leader(n)]
def update(self, n, a):
self.A[self.leader(n)] = a
def same(self, a, b):
return self.leader(a) == self.leader(b)
def size(self, a):
return abs(self.parent_size[self.leader(a)])
def groups(self):
result = [[] for _ in range(self.n)]
for i in range(self.n):
result[self.leader(i)].append(i)
return [r for r in result if r != []]
・ランレングス圧縮
def RLE(A):
ans = []
cnt = 0
for i in range(len(A)):
cnt += 1
if i+1 == len(A) or A[i] != A[i+1]:
ans.append((A[i], cnt))
cnt = 0
return ans
def RLER(A):
ans = []
for s, c in A:
ans.append(s*c)
return "".join(ans)
・Manacher
def Manacher(S):
C = [""]
for s in S:
C.append(s)
C.append("")
R = [0]*len(C)
i = 0
j = 0
while i < len(C):
while 0 <= i-j and i+j < len(C) and C[i-j] == C[i+j]:
j += 1
R[i] = j
k = 1
while 0 <= i-k and k+R[i-k] < j:
R[i+k] = R[i-k]
k += 1
i += k
j -= k
odd = []
even = []
for i in range(1, len(C)-1):
if i%2 == 1:
odd.append(R[i]//2)
else:
even.append(R[i]//2)
return odd, even
・凸包
def cross3(a, b, c):
return (b[0]-a[0])*(c[1]-a[1]) - (b[1]-a[1])*(c[0]-a[0])
def convex_hull(ps):
ps.sort()
qs = []
L = len(ps)
for p in ps:
# 一直線上で高々2点にする場合は ">=" にする
while len(qs) > 1 and cross3(qs[-1], qs[-2], p) > 0:
qs.pop()
qs.append(p)
t = len(qs)
for i in range(L-2, -1, -1):
p = ps[i]
while len(qs) > t and cross3(qs[-1], qs[-2], p) > 0:
qs.pop()
qs.append(p)
return qs
A = []
IN = [-1]*N
OUT = [-1]*N
dfs(0, -1, 0)
・Auxiliary Tree
class AuxiliaryTree:
def __init__(self, N, G):
self.N = N
self.G = G
self.IN = [0]*N
self.OUT = [0]*N
self.depth = [0]*N
self.E = []
self.dfs(0, -1, 0)
self.L = len(self.E)
self.lg = [0]*(self.L+1)
self.make_sparse_table()
@bootstrap
def dfs(self, n, p, d):
self.depth[n] = d
self.IN[n] = len(self.E)
self.E.append(n)
for v in self.G[n]:
if v == p:
continue
yield self.dfs(v, n, d+1)
self.E.append(n)
self.OUT[n] = len(self.E)
self.E.append(n)
yield
def make_sparse_table(self):
for i in range(2, self.L+1):
self.lg[i] = self.lg[i>>1]+1
self.st = [[self.L]*(self.L-(1<<i)+1) for i in range(self.lg[self.L]+1)]
self.st[0] = self.E[:]
b = 1
for i in range(self.lg[self.L]):
for j in range(self.L-(b<<1)+1):
self.st[i+1][j] = (self.st[i][j] if self.depth[self.st[i][j]] <= self.depth[self.st[i][j+b]] else self.st[i][j+b])
b <<= 1
def lca(self, u, v):
x, y = self.IN[u], self.IN[v]
l = self.lg[y-x+1]
return self.st[l][x] if self.depth[self.st[l][x]] <= self.depth[self.st[l][y-(1<<l)+1]] else self.st[l][y-(1<<l)+1]
def query(self, v):
nG = defaultdict(list)
V = v[:]
V.sort(key=self.IN.__getitem__)
K = len(V)
stack = [V[0]]
for i in range(K-1):
w = self.lca(V[i], V[i+1])
if w != V[i]:
last = stack.pop()
while stack and self.depth[w] < self.depth[stack[-1]]:
d = abs(self.depth[stack[-1]]-self.depth[last])
nG[stack[-1]].append((last, d))
nG[last].append((stack[-1], d))
last = stack.pop()
if not stack or stack[-1] != w:
stack.append(w)
V.append(w)
d = abs(self.depth[w]-self.depth[last])
nG[w].append((last, d))
nG[last].append((w, d))
stack.append(V[i+1])
for i in range(len(stack)-1):
d = abs(self.depth[stack[i]]-self.depth[stack[i+1]])
nG[stack[i]].append((stack[i+1], d))
nG[stack[i+1]].append((stack[i], d))
return nG, stack[0]
・木の直径と重心
visited = [-1]*N
visited[0] = 0
que = deque()
que.append(0)
while que:
n = que.popleft()
for v in G[n]:
if visited[v] == -1:
visited[v] = visited[n]+1
que.append(v)
idx = visited.index(max(visited))
visited = [-1]*N
visited[idx] = 0
pre = [-1]*N
que = deque()
que.append(idx)
while que:
n = que.popleft()
for v in G[n]:
if visited[v] == -1:
visited[v] = visited[n]+1
que.append(v)
pre[v] = n
D = max(visited)
idx = visited.index(D)
while visited[idx] > (D+1)//2:
idx = pre[idx]
center1 = idx
center2 = -1
if D%2 == 1:
center2 = pre[idx]
・高速フーリエ変換
class FFT():
def primitive_root_constexpr(self,m):
if m==2:return 1
if m==167772161:return 3
if m==469762049:return 3
if m==754974721:return 11
if m==998244353:return 3
divs=[0]*20
divs[0]=2
cnt=1
x=(m-1)//2
while(x%2==0):x//=2
i=3
while(i*i<=x):
if (x%i==0):
divs[cnt]=i
cnt+=1
while(x%i==0):
x//=i
i+=2
if x>1:
divs[cnt]=x
cnt+=1
g=2
while(1):
ok=True
for i in range(cnt):
if pow(g,(m-1)//divs[i],m)==1:
ok=False
break
if ok:
return g
g+=1
def bsf(self,x):
res=0
while(x%2==0):
res+=1
x//=2
return res
rank2=0
root=[]
iroot=[]
rate2=[]
irate2=[]
rate3=[]
irate3=[]
def __init__(self,MOD):
self.mod=MOD
self.g=self.primitive_root_constexpr(self.mod)
self.rank2=self.bsf(self.mod-1)
self.root=[0 for i in range(self.rank2+1)]
self.iroot=[0 for i in range(self.rank2+1)]
self.rate2=[0 for i in range(self.rank2)]
self.irate2=[0 for i in range(self.rank2)]
self.rate3=[0 for i in range(self.rank2-1)]
self.irate3=[0 for i in range(self.rank2-1)]
self.root[self.rank2]=pow(self.g,(self.mod-1)>>self.rank2,self.mod)
self.iroot[self.rank2]=pow(self.root[self.rank2],self.mod-2,self.mod)
for i in range(self.rank2-1,-1,-1):
self.root[i]=(self.root[i+1]**2)%self.mod
self.iroot[i]=(self.iroot[i+1]**2)%self.mod
prod=1;iprod=1
for i in range(self.rank2-1):
self.rate2[i]=(self.root[i+2]*prod)%self.mod
self.irate2[i]=(self.iroot[i+2]*iprod)%self.mod
prod=(prod*self.iroot[i+2])%self.mod
iprod=(iprod*self.root[i+2])%self.mod
prod=1;iprod=1
for i in range(self.rank2-2):
self.rate3[i]=(self.root[i+3]*prod)%self.mod
self.irate3[i]=(self.iroot[i+3]*iprod)%self.mod
prod=(prod*self.iroot[i+3])%self.mod
iprod=(iprod*self.root[i+3])%self.mod
def butterfly(self,a):
n=len(a)
h=(n-1).bit_length()
LEN=0
while(LEN<h):
if (h-LEN==1):
p=1<<(h-LEN-1)
rot=1
for s in range(1<<LEN):
offset=s<<(h-LEN)
for i in range(p):
l=a[i+offset]
r=a[i+offset+p]*rot
a[i+offset]=(l+r)%self.mod
a[i+offset+p]=(l-r)%self.mod
rot*=self.rate2[(~s & -~s).bit_length()-1]
rot%=self.mod
LEN+=1
else:
p=1<<(h-LEN-2)
rot=1
imag=self.root[2]
for s in range(1<<LEN):
rot2=(rot*rot)%self.mod
rot3=(rot2*rot)%self.mod
offset=s<<(h-LEN)
for i in range(p):
a0=a[i+offset]
a1=a[i+offset+p]*rot
a2=a[i+offset+2*p]*rot2
a3=a[i+offset+3*p]*rot3
a1na3imag=(a1-a3)%self.mod*imag
a[i+offset]=(a0+a2+a1+a3)%self.mod
a[i+offset+p]=(a0+a2-a1-a3)%self.mod
a[i+offset+2*p]=(a0-a2+a1na3imag)%self.mod
a[i+offset+3*p]=(a0-a2-a1na3imag)%self.mod
rot*=self.rate3[(~s & -~s).bit_length()-1]
rot%=self.mod
LEN+=2
def butterfly_inv(self,a):
n=len(a)
h=(n-1).bit_length()
LEN=h
while(LEN):
if (LEN==1):
p=1<<(h-LEN)
irot=1
for s in range(1<<(LEN-1)):
offset=s<<(h-LEN+1)
for i in range(p):
l=a[i+offset]
r=a[i+offset+p]
a[i+offset]=(l+r)%self.mod
a[i+offset+p]=(l-r)*irot%self.mod
irot*=self.irate2[(~s & -~s).bit_length()-1]
irot%=self.mod
LEN-=1
else:
p=1<<(h-LEN)
irot=1
iimag=self.iroot[2]
for s in range(1<<(LEN-2)):
irot2=(irot*irot)%self.mod
irot3=(irot*irot2)%self.mod
offset=s<<(h-LEN+2)
for i in range(p):
a0=a[i+offset]
a1=a[i+offset+p]
a2=a[i+offset+2*p]
a3=a[i+offset+3*p]
a2na3iimag=(a2-a3)*iimag%self.mod
a[i+offset]=(a0+a1+a2+a3)%self.mod
a[i+offset+p]=(a0-a1+a2na3iimag)*irot%self.mod
a[i+offset+2*p]=(a0+a1-a2-a3)*irot2%self.mod
a[i+offset+3*p]=(a0-a1-a2na3iimag)*irot3%self.mod
irot*=self.irate3[(~s & -~s).bit_length()-1]
irot%=self.mod
LEN-=2
def convolution(self,a,b):
n=len(a);m=len(b)
if not(a) or not(b):
return []
if min(n,m)<=40:
res=[0]*(n+m-1)
for i in range(n):
for j in range(m):
res[i+j]+=a[i]*b[j]
res[i+j]%=self.mod
return res
z=1<<((n+m-2).bit_length())
a=a+[0]*(z-n)
b=b+[0]*(z-m)
self.butterfly(a)
self.butterfly(b)
c=[(a[i]*b[i])%self.mod for i in range(z)]
self.butterfly_inv(c)
iz=pow(z,self.mod-2,self.mod)
for i in range(n+m-1):
c[i]=(c[i]*iz)%self.mod
return c[:n+m-1]
・分数
from math import gcd
class Fraction:
def __init__(self, top, bottom):
if bottom == 0:
raise ZeroDivisionError
GCD = gcd(top, bottom)
if bottom < 0:
top = -top
bottom = -bottom
self.top = top//GCD
self.bottom = bottom//GCD
def _to_fraction(self, x):
return x if isinstance(x, Fraction) else Fraction(x, 1)
def __eq__(self, other):
other = self._to_fraction(other)
return self.top == other.top and self.bottom == other.bottom
def __ne__(self, other):
other = self._to_fraction(other)
return self.top != other.top or self.bottom != other.bottom
def __lt__(self, other):
other = self._to_fraction(other)
return self.top*other.bottom < self.bottom*other.top
def __le__(self, other):
other = self._to_fraction(other)
return self.top*other.bottom <= self.bottom*other.top
def __gt__(self, other):
other = self._to_fraction(other)
return self.top*other.bottom > self.bottom*other.top
def __ge__(self, other):
other = self._to_fraction(other)
return self.top*other.bottom >= self.bottom*other.top
def __add__(self, other):
other = self._to_fraction(other)
GCD = gcd(self.bottom, other.bottom)
bottom = self.bottom*other.bottom//GCD
top1 = self.top*(bottom//self.bottom)
top2 = other.top*(bottom//other.bottom)
return Fraction(top1+top2, bottom)
def __sub__(self, other):
other = self._to_fraction(other)
GCD = gcd(self.bottom, other.bottom)
bottom = self.bottom*other.bottom//GCD
top1 = self.top*(bottom//self.bottom)
top2 = other.top*(bottom//other.bottom)
return Fraction(top1-top2, bottom)
def __mul__(self, other):
other = self._to_fraction(other)
return Fraction(self.top*other.top, self.bottom*other.bottom)
def __truediv__(self, other):
other = self._to_fraction(other)
return Fraction(self.top*other.bottom, self.bottom*other.top)
def __radd__(self, other):
return self+other
def __rsub__(self, other):
return self._to_fraction(other)-self
def __rmul__(self, other):
return self*other
def __rtruediv__(self, other):
return self._to_fraction(other)/self
def __int__(self):
return self.top//self.bottom
def __float__(self):
return self.top/self.bottom
def __str__(self):
return f"{self.top}/{self.bottom}"
def __hash__(self):
return hash((self.top, self.bottom))
def __bool__(self):
return self.top != 0
def __neg__(self):
return Fraction(-self.top, self.bottom)
def __abs__(self):
return Fraction(abs(self.top), self.bottom)
def get(self):
return self.top, self.bottom
・ランダムチェッカー
from random import randrange
def solve1(N, L, R, A):
# 自分のプログラム
pass
def solve2(N, L, R, A):
# 愚直のプログラム
pass
while True:
# 入力データをランダムで生成する
# 違う出力をした場合に出力して終了する
if solve1() != solve2():
break
・floor_sum
def floor_sum(n, m, a, b):
ans = 0
while True:
if a >= m or a < 0:
ans += n * (n - 1) * (a // m) // 2
a %= m
if b >= m or b < 0:
ans += n * (b // m)
b %= m
y_max = a * n + b
if y_max < m: break
n, b, m, a = y_max // m, y_max % m, a, m
return ans
・ハッシュ（Hack対策）
from random import randrange
H = randrange(1, 1<<60)
def Hash(n):
return n^H
・ChatGPT 翻訳依頼
今からCodeforcesの問題文を与えるため、日本語に翻訳してください。
翻訳以外の用途で生成AIを使用することは禁止されているため、問題の解法については出力しないようにしてください。
・Convex Hull Trick（O(N)）
class Convex_Hull_Trick:
def __init__(self):
self.que = deque()
def check(self, f1, f2, f3):
return (f2[0] - f1[0]) * (f3[1] - f2[1]) >= (f2[1] - f1[1]) * (f3[0] - f2[0])
def f(self, f1, x):
return f1[0]*x + f1[1]
# add f_i(x) = a*x + b
# 降順
def add_line(self, a, b):
f1 = (a, b)
while len(self.que) >= 2 and self.check(self.que[-2], self.que[-1], f1):
self.que.pop()
self.que.append(f1)
# min f_i(x)
# 昇順
def query(self, x):
while len(self.que) >= 2 and self.f(self.que[0], x) >= self.f(self.que[1], x):
self.que.popleft()
return self.f(self.que[0], x)
・セグメント木（区間演算、一点取得）
def op(x, y):
return
class SegTree:
def __init__(self, init_val, op, ide_ele):
n = len(init_val)
self.n = n
self.op = op
self.ide_ele = ide_ele
self.num = 1 << (n - 1).bit_length()
self.tree = [ide_ele] * 2 * self.num
for i in range(n):
self.tree[self.num + i] = init_val[i]
def update(self, l, r, x):
l += self.num
r += self.num
while l < r:
if l & 1:
self.tree[l] = self.op(x, self.tree[l])
l += 1
if r & 1:
self.tree[r - 1] = self.op(x, self.tree[r - 1])
l >>= 1
r >>= 1
def query(self, k):
ans = self.ide_ele
k += self.num
ans = self.op(ans, self.tree[k])
while k > 1:
ans = self.op(ans, self.tree[k>>1])
k >>= 1
return ans
・セグメント木（区間更新、一点取得）
class SegTree:
def __init__(self, init_val):
n = len(init_val)
self.n = n
self.num = 1 << (n - 1).bit_length()
self.tree = [-1] * 2 * self.num
self.rank = [-1] * 2 * self.num
self.cnt = 0
for i in range(n):
self.tree[self.num + i] = init_val[i]
self.rank[self.num + i] = self.cnt
self.cnt += 1
def update(self, l, r, x):
l += self.num
r += self.num
while l < r:
if l & 1:
self.tree[l] = x
self.rank[l] = self.cnt
l += 1
if r & 1:
self.tree[r - 1] = x
self.rank[r - 1] = self.cnt
l >>= 1
r >>= 1
self.cnt += 1
def query(self, k):
k += self.num
ans = self.tree[k]
MAX = self.rank[k]
while k > 1:
if MAX < self.rank[k>>1]:
ans = self.tree[k>>1]
MAX = self.rank[k>>1]
k >>= 1
return ans
・区間XOR
def XORSUM(n):
if n%4 == 0:
return n
elif n%4 == 1:
return 1
elif n%4 == 2:
return n+1
else:
return 0
def rangeXOR(l, r):
return XORSUM(r)^XORSUM(l-1)
・BucketList(tatyam)
# https://github.com/tatyam-prime/SortedSet/blob/main/BucketList.py
import math
from typing import Generic, Iterable, Iterator, TypeVar
T = TypeVar('T')
class BucketList(Generic[T]):
BUCKET_RATIO = 16
SPLIT_RATIO = 24
def __init__(self, a: Iterable[T] = []) -> None:
a = list(a)
n = self.size = len(a)
num_bucket = int(math.ceil(math.sqrt(n / self.BUCKET_RATIO)))
self.a = [a[n * i // num_bucket : n * (i + 1) // num_bucket] for i in range(num_bucket)]
def __iter__(self) -> Iterator[T]:
for i in self.a:
for j in i: yield j
def __reversed__(self) -> Iterator[T]:
for i in reversed(self.a):
for j in reversed(i): yield j
def __eq__(self, other) -> bool:
if len(self) != len(other): return False
for x, y in zip(self, other):
if x != y: return False
return True
def __len__(self) -> int:
return self.size
def __repr__(self) -> str:
return "BucketList" + str(self.a)
def __str__(self) -> str:
return str(list(self))
def __contains__(self, x: T) -> bool:
"Return True if x is in the bucket list. / O(N)"
for y in self:
if x == y: return True
return False
def _insert(self, a: list[T], b: int, i: int, x: T) -> None:
a.insert(i, x)
self.size += 1
if len(a) > len(self.a) * self.SPLIT_RATIO:
mid = len(a) >> 1
self.a[b:b+1] = [a[:mid], a[mid:]]
def insert(self, i: int, x: T) -> None:
"Insert x at the i-th position. / O(√N)"
if self.size == 0:
if i != 0 and i != -1: raise IndexError
self.a = [[x]]
self.size = 1
return
if i < 0:
for b, a in enumerate(reversed(self.a)):
i += len(a)
if i >= 0: return self._insert(a, len(self.a) + ~b, i, x)
else:
for b, a in enumerate(self.a):
if i <= len(a): return self._insert(a, b, i, x)
i -= len(a)
raise IndexError
def append(self, x: T) -> None:
"Append x to the end of the list. / amortized O(1)"
if self.size == 0:
self.a = [[x]]
self.size = 1
return
a = self.a[-1]
return self._insert(a, len(self.a) - 1, len(a), x)
def extend(self, a: Iterable[T]) -> None:
for x in a: self.append(x)
def __getitem__(self, i: int) -> T:
if i < 0:
for a in reversed(self.a):
i += len(a)
if i >= 0: return a[i]
else:
for a in self.a:
if i < len(a): return a[i]
i -= len(a)
raise IndexError
def _pop(self, a: list[T], b: int, i: int) -> T:
ans = a.pop(i)
self.size -= 1
if not a: del self.a[b]
return ans
def pop(self, i: int = -1) -> T:
"Remove and return the i-th element. / O(√N) / O(-i) if i < 0"
if i < 0:
for b, a in enumerate(reversed(self.a)):
i += len(a)
if i >= 0: return self._pop(a, ~b, i)
else:
for b, a in enumerate(self.a):
if i < len(a): return self._pop(a, b, i)
i -= len(a)
raise IndexError
def count(self, x: T) -> int:
"Return the number of occurrences of x. / O(N)"
return sum(1 for y in self if x == y)
def index(self, x: T) -> int:
"Return the index of the first occurrence of x, raise ValueError if not found. / O(N)"
for i, y in enumerate(self):
if x == y: return i
raise ValueError
def remove(self, x: T) -> None:
"Remove the first occurrence of x, raise ValueError if not found. / O(N)"
self.pop(self.index(x))
def clear(self) -> None:
self.a = []
self.size = 0
def reverse(self) -> None:
self.a.reverse()
for a in self.a: a.reverse()
def copy(self) -> 'BucketList[T]':
return BucketList(self)
・Lucasの定理
class Lucas:
def __init__(self, MOD):
self.MOD = MOD
self.comb = [[0]*self.MOD for _ in range(self.MOD)]
self.comb[0][0] = 1
for i in range(1, self.MOD):
self.comb[i][0] = 1
for j in range(1, i+1):
self.comb[i][j] = (self.comb[i-1][j-1]+self.comb[i-1][j])%self.MOD
def C(self, N, K):
ans = 1
while N:
ans *= self.comb[N%self.MOD][K%self.MOD]
ans %= self.MOD
N //= self.MOD
K //= self.MOD
return ans
・ラベル
class Label:
def __init__(self, N, A=[]):
self.N = N
if A:
self.label = A[:]
else:
self.label = list(range(N))
self.labelR = [-1]*self.N
for i in range(self.N):
self.labelR[self.label[i]] = i
# ラベルがどの箱に貼られているか
def __getitem__(self, n):
return self.labelR[n]
# 箱に貼られているラベルは何か
def getLabel(self, n):
return self.label[n]
# ラベルの情報を元にスワップ
def swap(self, l, r):
self.label[self.labelR[l]], self.label[self.labelR[r]] = self.label[self.labelR[r]], self.label[self.labelR[l]]
self.labelR[l], self.labelR[r] = self.labelR[r], self.labelR[l]
・動的セグメントツリー
class Node:
def __init__(self, init_val):
self.left = None
self.right = None
self.value = init_val
def op(x, y):
if x[0]%2 == 0:
return (x[0]+y[0], x[1]+y[1], x[2]+y[2])
else:
return (x[0]+y[0], x[1]+y[2], x[2]+y[1])
class DynamicSegmentTree:
def __init__(self, L, R, op, init_val):
self.root = Node(init_val)
self.L = L
self.R = R
self.op = op
self.init_val = init_val
def update(self, idx, value):
stack = [(self.root, self.L, self.R)]
path = []
while stack:
node, s, e = stack.pop()
path.append((node, s, e))
if s == e:
node.value = value
break
mid = (s+e)//2
if idx <= mid:
if not node.left:
node.left = Node(self.init_val)
stack.append((node.left, s, mid))
else:
if not node.right:
node.right = Node(self.init_val)
stack.append((node.right, mid+1, e))
path.pop()
while path:
node, s, e = path.pop()
node.value = self.op(node.left.value if node.left else self.init_val, node.right.value if node.right else self.init_val)
def query(self, l, r):
stack = [(self.root, self.L, self.R)]
ans = self.init_val
while stack:
node, s, e = stack.pop()
if not node or e < l or r < s:
continue
if l <= s and e <= r:
ans = self.op(ans, node.value)
continue
mid = (s+e)//2
stack.append((node.left, s, mid))
stack.append((node.right, mid+1, e))
return ans
・最大流
# https://github.com/not522/ac-library-python/blob/master/atcoder/maxflow.py
from typing import NamedTuple, Optional, List, cast
class MFGraph:
class Edge(NamedTuple):
src: int
dst: int
cap: int
flow: int
class _Edge:
def __init__(self, dst: int, cap: int) -> None:
self.dst = dst
self.cap = cap
self.rev: Optional[MFGraph._Edge] = None
def __init__(self, n: int) -> None:
self._n = n
self._g: List[List[MFGraph._Edge]] = [[] for _ in range(n)]
self._edges: List[MFGraph._Edge] = []
def add_edge(self, src: int, dst: int, cap: int) -> int:
assert 0 <= src < self._n
assert 0 <= dst < self._n
assert 0 <= cap
m = len(self._edges)
e = MFGraph._Edge(dst, cap)
re = MFGraph._Edge(src, 0)
e.rev = re
re.rev = e
self._g[src].append(e)
self._g[dst].append(re)
self._edges.append(e)
return m
def get_edge(self, i: int) -> Edge:
assert 0 <= i < len(self._edges)
e = self._edges[i]
re = cast(MFGraph._Edge, e.rev)
return MFGraph.Edge(
re.dst,
e.dst,
e.cap + re.cap,
re.cap
)
def edges(self) -> List[Edge]:
return [self.get_edge(i) for i in range(len(self._edges))]
def change_edge(self, i: int, new_cap: int, new_flow: int) -> None:
assert 0 <= i < len(self._edges)
assert 0 <= new_flow <= new_cap
e = self._edges[i]
e.cap = new_cap - new_flow
assert e.rev is not None
e.rev.cap = new_flow
def flow(self, s: int, t: int, flow_limit: Optional[int] = None) -> int:
assert 0 <= s < self._n
assert 0 <= t < self._n
assert s != t
if flow_limit is None:
flow_limit = cast(int, sum(e.cap for e in self._g[s]))
current_edge = [0] * self._n
level = [0] * self._n
def fill(arr: List[int], value: int) -> None:
for i in range(len(arr)):
arr[i] = value
def bfs() -> bool:
fill(level, self._n)
queue = []
q_front = 0
queue.append(s)
level[s] = 0
while q_front < len(queue):
v = queue[q_front]
q_front += 1
next_level = level[v] + 1
for e in self._g[v]:
if e.cap == 0 or level[e.dst] <= next_level:
continue
level[e.dst] = next_level
if e.dst == t:
return True
queue.append(e.dst)
return False
def dfs(lim: int) -> int:
stack = []
edge_stack: List[MFGraph._Edge] = []
stack.append(t)
while stack:
v = stack[-1]
if v == s:
flow = min(lim, min(e.cap for e in edge_stack))
for e in edge_stack:
e.cap -= flow
assert e.rev is not None
e.rev.cap += flow
return flow
next_level = level[v] - 1
while current_edge[v] < len(self._g[v]):
e = self._g[v][current_edge[v]]
re = cast(MFGraph._Edge, e.rev)
if level[e.dst] != next_level or re.cap == 0:
current_edge[v] += 1
continue
stack.append(e.dst)
edge_stack.append(re)
break
else:
stack.pop()
if edge_stack:
edge_stack.pop()
level[v] = self._n
return 0
flow = 0
while flow < flow_limit:
if not bfs():
break
fill(current_edge, 0)
while flow < flow_limit:
f = dfs(flow_limit - flow)
flow += f
if f == 0:
break
return flow
def min_cut(self, s: int) -> List[bool]:
visited = [False] * self._n
stack = [s]
visited[s] = True
while stack:
v = stack.pop()
for e in self._g[v]:
if e.cap > 0 and not visited[e.dst]:
visited[e.dst] = True
stack.append(e.dst)
return visited
・Gauss-Jordanの掃き出し法（MOD）
def GaussJordan_MOD(A, is_extended):
H, W = len(A), len(A[0])
for i in range(H):
for j in range(W):
A[i][j] %= MOD
rank = 0
for j in range(W-is_extended):
for i in range(rank, H):
if A[i][j] != 0:
pivot = i
break
else:
continue
A[pivot], A[rank] = A[rank], A[pivot]
inv = pow(A[rank][j], -1, MOD)
for i in range(W):
A[rank][i] *= inv
A[rank][i] %= MOD
for i in range(H):
if i == rank or A[i][j] == 0:
continue
mul = A[i][j]
for k in range(W):
A[i][k] -= A[rank][k]*mul%MOD
A[i][k] %= MOD
rank += 1
return rank
・連立方程式（GaussJordan）
def linear_equation(A, B):
H, W = len(A), len(A[0])
for i in range(H):
A[i].append(B[i])
rank = GaussJordan_MOD(A, True)
for i in range(rank, H):
if A[i][W]:
return None, None
ans = [A[i][W] for i in range(rank)]
C = A[:rank]
for i in range(rank):
C[i].pop()
return C, ans
・二項係数（Nが大きいとき用）
def C(N, K):
if N < K:
return 0
if N < K*2:
K = N-K
top = 1
for i in range(N, N-K, -1):
top *= i
top %= MOD
bottom = 1
for i in range(1, K+1):
bottom *= i
bottom %= MOD
return inverse(top, bottom)
・BinaryTrie
class BinaryTrie:
def __init__(self, length):
self.tree = [[-1]*2]
self.arrive = [0]
self.last = [0]
self.nex = 1
self.length = length
self.all_xor = 0
def BIT(self, bit, n):
return bit>>n & 1
def operate_xor(self, n):
self.all_xor ^= n
def count(self):
return self.arrive[0]
def find(self, n):
now = 0
for i in reversed(range(self.length)):
nex = self.BIT(n, i)^self.BIT(self.all_xor, i)
if self.tree[now][nex] != -1 and 1 <= self.arrive[self.tree[now][nex]]:
now = self.tree[now][self.BIT(n, i)^self.BIT(self.all_xor, i)]
else:
return False
return True
def insert(self, n):
now = 0
self.arrive[now] += 1
for i in reversed(range(self.length)):
if self.tree[now][self.BIT(n, i)^self.BIT(self.all_xor, i)] == -1:
self.tree[now][self.BIT(n, i)^self.BIT(self.all_xor, i)] = self.nex
self.tree.append([-1]*2)
self.arrive.append(0)
self.last.append(0)
now = self.nex
self.nex += 1
else:
now = self.tree[now][self.BIT(n, i)^self.BIT(self.all_xor, i)]
self.arrive[now] += 1
self.last[now] += 1
def delete(self, n):
# 存在していることが前提
now = 0
self.arrive[now] -= 1
for i in reversed(range(self.length)):
now = self.tree[now][self.BIT(n, i)^self.BIT(self.all_xor, i)]
self.arrive[now] -= 1
self.last[now] -= 1
def min_element(self, n=0):
if self.count() == 0:
return -1
ans = 0
now = 0
for i in reversed(range(self.length)):
bit = self.BIT(n, i)^self.BIT(self.all_xor, i)
nex = self.tree[now][bit]
if nex != -1 and 1 <= self.arrive[nex]:
now = nex
if bit:
ans |= 1<<i
else:
now = self.tree[now][bit^1]
if not bit:
ans |= 1<<i
return ans^self.all_xor
def max_element(self, n=0):
if self.count() == 0:
return -1
ans = 0
now = 0
for i in reversed(range(self.length)):
bit = self.BIT(n, i)^self.BIT(self.all_xor, i)^1
nex = self.tree[now][bit]
if nex != -1 and 1 <= self.arrive[nex]:
now = nex
if bit:
ans |= 1<<i
else:
now = self.tree[now][bit^1]
if not bit:
ans |= 1<<i
return ans^self.all_xor
def kth_smallest(self, k, n=0):
k += 1
if self.count() < k:
return -1
ans = 0
now = 0
for i in reversed(range(self.length)):
bit = self.BIT(n, i)^self.BIT(self.all_xor, i)
nex = self.tree[now][bit]
if nex != -1 and k <= self.arrive[nex]:
now = nex
if bit:
ans |= 1<<i
else:
now = self.tree[now][bit^1]
k -= self.arrive[nex] if nex != -1 else 0
if not bit:
ans |= 1<<i
return ans^self.all_xor
def kth_largest(self, k, n=0):
k += 1
if self.count() < k:
return -1
ans = 0
now = 0
for i in reversed(range(self.length)):
bit = self.BIT(n, i)^self.BIT(self.all_xor, i)^1
nex = self.tree[now][bit]
if nex != -1 and k <= self.arrive[nex]:
now = nex
if bit:
ans |= 1<<i
else:
now = self.tree[now][bit^1]
k -= self.arrive[nex] if nex != -1 else 0
if not bit:
ans |= 1<<i
return ans^self.all_xor
def freq(self, n):
now = 0
for i in reversed(range(self.length)):
bit = self.BIT(n, i)^self.BIT(self.all_xor, i)
if self.tree[now][bit] == -1:
return 0
now = self.tree[now][bit]
return self.last[now]
・直線の方程式
def line_equation(x1, y1, x2, y2):
a = y2-y1
b = x1-x2
c = x2*y1-x1*y2
return a, b, c
・IntervalSet
class IntervalSet:
def __init__(self):
self.interval = SortedMultiset()
def add(self, l, r):
idx = self.interval.index((l, -1))
cnt = r-l+1
if 1 <= idx and l <= self.interval[idx-1][1]+1:
l2, r2 = self.interval.pop(idx-1)
cnt -= min(r2, r)-l+1
idx -= 1
l = l2
r = max(r2, r)
while idx < len(self.interval) and self.interval[idx][0] <= r+1:
l2, r2 = self.interval.pop(idx)
cnt -= min(r2, r)-l2+1
r = max(r, r2)
self.interval.add((l, r))
return cnt
def remove(self, l, r):
idx = self.interval.index((l, -1))
cnt = 0
if 1 <= idx and l <= self.interval[idx-1][1]:
l2, r2 = self.interval.pop(idx-1)
cnt += min(r, r2)-l+1
self.interval.add((l2, l-1))
if r < r2:
self.interval.add((r+1, r2))
while idx < len(self.interval) and self.interval[idx][0] <= r:
l2, r2 = self.interval.pop(idx)
cnt += min(r2, r)-l2+1
if r < r2:
self.interval.add((r+1, r2))
return cnt
def add2(self, l, r):
ans = []
idx = self.interval.index((l, -1))
pl = l
if 1 <= idx and l <= self.interval[idx-1][1]+1:
l2, r2 = self.interval.pop(idx-1)
idx -= 1
l = l2
r = max(r2, r)
pl = r2+1
while idx < len(self.interval) and self.interval[idx][0] <= r+1:
l2, r2 = self.interval.pop(idx)
if pl < l2:
ans.append((pl, l2-1))
pl = r2+1
r = max(r, r2)
self.interval.add((l, r))
if pl <= r:
ans.append((pl, r))
return ans
def remove2(self, l, r):
ans = []
idx = self.interval.index((l, -1))
if 1 <= idx and l <= self.interval[idx-1][1]:
l2, r2 = self.interval.pop(idx-1)
self.interval.add((l2, l-1))
ans.append((l, min(r2, r)))
if r < r2:
self.interval.add((r+1, r2))
while idx < len(self.interval) and self.interval[idx][0] <= r:
l2, r2 = self.interval.pop(idx)
ans.append((l2, min(r2, r)))
if r < r2:
self.interval.add((r+1, r2))
return ans
def find(self, x):
idx = self.interval.index((x+1, -1))
if idx == 0:
return (-1, -1)
l, r = self.interval[idx-1]
if x <= r:
return (l, r)
else:
return (-1, -1)
・Mo's algorithm
class Mo:
def __init__(self, N, add_L, add_R, remove_L, remove_R, route=None):
self.N = N
self.add_L = add_L
self.add_R = add_R
self.remove_L = remove_L
self.remove_R = remove_R
self.route = route if route is not None else int(self.N**0.5)+1
def solve(self, query):
Q = len(query)
bucket = [[] for _ in range(self.N//self.route+1)]
for i, (l, r) in enumerate(query):
l, r = l-1, r-1
bucket[l//self.route].append((i, l, r))
ans = [-1]*Q
now = 0
left = 0
right = -1
for idx, q in enumerate(bucket):
for i, l, r in sorted(q, key=lambda x:x[2], reverse=idx%2):
while l < left:
left -= 1
now = self.add_L(now, left)
while right < r:
right += 1
now = self.add_R(now, right)
while left < l:
now = self.remove_L(now, left)
left += 1
while r < right:
now = self.remove_R(now, right)
right -= 1
ans[i] = now
return ans
・Baby-step Giant-step
def BSGS(A, G, P):
route = isqrt(P)+1
D = dict()
SUM = 1
for i in range(route):
if SUM not in D:
D[SUM] = i
SUM *= A
SUM %= P
C = pow(A, -route, P)
for i in range(route):
if G in D:
return route*i+D[G]
G *= C
G %= P
else:
return -1
・DSU on Tree
@bootstrap
def get_size(n, p):
for v in G[n]:
if v == p:
continue
yield get_size(v, n)
size[n] += size[v]
yield
size = [1]*N
get_size(0, -1)
@bootstrap
def dfs(n, p, keep):
MAX, bigv = -1, -1
for v in G[n]:
if v == p:
continue
if MAX < size[v]:
MAX = size[v]
bigv = v
for v in G[n]:
if v == p or v == bigv:
continue
yield dfs(v, n, 0)
if bigv != -1:
yield dfs(bigv, n, 1)
A[n] = A[bigv]
for v in G[n]:
if v == p or v == bigv:
continue
for x in A[v]:
A[n].append(x)
A[n].append(n)
if keep == 0:
for v in A[n]:
pass
yield
A = [[] for _ in range(N)]
dfs(0, -1, 0)
・Suffix Automaton
class SuffixAutomaton:
class Node:
def __init__(self, nex, link, size):
self.nex = nex
self.link = link
self.size = size
def __init__(self, type):
self.nodes = [self.Node([-1]*26, -1, 0)]
self.ord_a = ord("a") if not type else ord("A")
self.last = 0
def alpha_code(self, s):
return ord(s)-self.ord_a
def push(self, c):
new_node = len(self.nodes)
code = self.alpha_code(c)
self.nodes.append(self.Node([-1]*26, -1, self.nodes[self.last].size+1))
p = self.last
while p != -1 and self.nodes[p].nex[code] == -1:
self.nodes[p].nex[code] = new_node
p = self.nodes[p].link
q = 0 if p == -1 else self.nodes[p].nex[code]
if p == -1 or self.nodes[p].size+1 == self.nodes[q].size:
self.nodes[new_node].link = q
else:
new_q = len(self.nodes)
self.nodes.append(self.Node(self.nodes[q].nex[:], self.nodes[q].link, self.nodes[p].size+1))
self.nodes[q].link = new_q
self.nodes[new_node].link = new_q
while p != -1 and self.nodes[p].nex[code] == q:
self.nodes[p].nex[code] = new_q
p = self.nodes[p].link
self.last = new_node
・SkewHeap
class SkewHeap:
class Node:
__slots__ = ("key", "l", "r")
def __init__(self, key):
self.key = key
self.l = None
self.r = None
def __init__(self, isMin=True):
self.isMin = isMin
def _comp(self, x, y):
if self.isMin:
return x.key < y.key
else:
return x.key > y.key
def meld(self, x, y):
if not x or not y:
return x if x else y
if not self._comp(x, y):
x, y = y, x
x.l = self.meld(x.l, y)
x.l, x.r = x.r, x.l
return x
def alloc(self, key):
return self.Node(key)
def push(self, x, key):
return self.meld(x, self.alloc(key))
def pop(self, x):
return self.meld(x.l, x.r)
・SkewHeap（遅延加算付き）
class SkewHeap:
class Node:
__slots__ = ("key", "laz", "l", "r")
def __init__(self, key):
self.key = key
self.laz = 0
self.l = None
self.r = None
def __init__(self, isMin=True):
self.isMin = isMin
def _propagate(self, x):
if x.laz == 0:
return
if x.l:
x.l.laz += x.laz
if x.r:
x.r.laz += x.laz
x.key += x.laz
x.laz = 0
def _comp(self, x, y):
if self.isMin:
return x.key+x.laz < y.key+y.laz
else:
return x.key+x.laz > y.key+y.laz
def meld(self, x, y):
if not x or not y:
return x if x else y
if not self._comp(x, y):
x, y = y, x
self._propagate(x)
x.l = self.meld(x.l, y)
x.l, x.r = x.r, x.l
return x
def alloc(self, key):
return self.Node(key)
def push(self, x, key):
return self.meld(x, self.alloc(key))
def pop(self, x):
self._propagate(x)
return self.meld(x.l, x.r)
def top(self, x):
self._propagate(x)
return x.key
def apply(self, x, laz):
x.laz += laz
self._propagate(x)
・Cartesian Tree
def CartesianTree(P):
stack = []
child = [[-1]*2 for _ in range(N)]
parent = [-1]*N
for i in range(N):
s = -1
while stack and P[i] < P[stack[-1]]:
s = stack.pop()
child[i][0] = s
if s != -1:
parent[s] = i
if stack:
parent[i] = stack[-1]
child[stack[-1]][1] = i
stack.append(i)
L, R = [-1]*N, [-1]*N
stack = [(P.index(min(P)), 0, N-1)]
while stack:
n, l, r = stack.pop()
L[n] = l
R[n] = r
a, b = child[n]
if a != -1:
stack.append((a, l, n-1))
if b != -1:
stack.append((b, n+1, r))
return child, parent, L, R
・ラグランジュ補間（係数）
def lagrange_interpolation_coef(X, Y):
N = len(X)-1
for i in range(N+1):
t = 1
for j in range(N+1):
if i != j:
t *= X[i]-X[j]
t %= MOD
Y[i] *= inverse(1, t)
Y[i] %= MOD
dp = [0]*(N+2)
dp[0] = 1
for i in range(N+1):
ndp = [0]*(N+2)
for j in range(N+2):
ndp[j] += dp[j]*(-X[i])%MOD
ndp[j] %= MOD
if 1 <= j:
ndp[j] += dp[j-1]
ndp[j] %= MOD
dp = ndp
ans = [0]*(N+1)
invX = []
for i in range(N+1):
if X[i] != 0:
invX.append(inverse(1, X[i]))
else:
invX.append(0)
for i in range(N+1):
if Y[i] == 0:
continue
if X[i] == 0:
for j in range(N+1):
ans[j] += dp[j+1]*Y[i]%MOD
ans[j] %= MOD
else:
ans[0] -= dp[0]*invX[i]%MOD*Y[i]%MOD
ans[0] %= MOD
pre = (-dp[0])*invX[i]%MOD
for j in range(1, N+1):
ans[j] -= (dp[j]-pre)*invX[i]%MOD*Y[i]%MOD
ans[j] %= MOD
pre = ((-(dp[j]-pre))*invX[i])%MOD
return ans
・ラグランジュ補間
def lagrange_interpolation(X, Y, T):
N = len(X)-1
ans = 0
for i in range(N+1):
t = 1
t_inv = 1
for j in range(N+1):
if i == j:
continue
t *= T-X[j]
t %= MOD
t_inv *= X[i]-X[j]
t_inv %= MOD
ans += inverse(t, t_inv)*Y[i]%MOD
ans %= MOD
return ans
・ラグランジュ補間（等差数列）
def lagrange_interpolation_arithmetic(a, d, Y, T):
# a = Xの初項 d = Xの交差
N = len(Y)-1
ans = 0
ft = 1
for i in range(N+1):
ft *= (T-(a+d*i))%MOD
ft %= MOD
f = 1
for i in range(1, N+1):
f *= -i*d%MOD
f %= MOD
ans += inverse(Y[0]*ft%MOD, f*(T-a)%MOD)
ans %= MOD
for i in range(N):
f *= inverse(d*(i+1), d*(i-N))
f %= MOD
ans += inverse(Y[i+1]*ft%MOD, f*(T-a-d*(i+1))%MOD)
ans %= MOD
return ans
・FPS
# https://github.com/atcoder/ac-library/blob/master/atcoder/convolution.hpp
from array import array
MOD = 998244353
IMAG = 911660635
IIMAG = 86583718
INV2 = 499122177
rate2 = array(
"I",
[
0,
911660635,
509520358,
369330050,
332049552,
983190778,
123842337,
238493703,
975955924,
603855026,
856644456,
131300601,
842657263,
730768835,
942482514,
806263778,
151565301,
510815449,
503497456,
743006876,
741047443,
56250497,
867605899,
0,
],
)
irate2 = array(
"I",
[
0,
86583718,
372528824,
373294451,
645684063,
112220581,
692852209,
155456985,
797128860,
90816748,
860285882,
927414960,
354738543,
109331171,
293255632,
535113200,
308540755,
121186627,
608385704,
438932459,
359477183,
824071951,
103369235,
0,
],
)
rate3 = array(
"I",
[
0,
372528824,
337190230,
454590761,
816400692,
578227951,
180142363,
83780245,
6597683,
70046822,
623238099,
183021267,
402682409,
631680428,
344509872,
689220186,
365017329,
774342554,
729444058,
102986190,
128751033,
395565204,
0,
],
)
irate3 = array(
"I",
[
0,
509520358,
929031873,
170256584,
839780419,
282974284,
395914482,
444904435,
72135471,
638914820,
66769500,
771127074,
985925487,
262319669,
262341272,
625870173,
768022760,
859816005,
914661783,
430819711,
272774365,
530924681,
0,
],
)
# https://judge.yosupo.jp/submission/55648
def butterfly(a: list):
n = len(a)
h = (n - 1).bit_length()
le = 0
while le < h:
if h - le == 1:
p = 1 << (h - le - 1)
rot = 1
for s in range(1 << le):
offset = s << (h - le)
for i in range(p):
l = a[i + offset]
r = a[i + offset + p] * rot
a[i + offset] = (l + r) % MOD
a[i + offset + p] = (l - r) % MOD
rot *= rate2[(~s & -~s).bit_length()]
rot %= MOD
le += 1
else:
p = 1 << (h - le - 2)
rot = 1
for s in range(1 << le):
rot2 = rot * rot % MOD
rot3 = rot2 * rot % MOD
offset = s << (h - le)
for i in range(p):
a0 = a[i + offset]
a1 = a[i + offset + p] * rot
a2 = a[i + offset + p * 2] * rot2
a3 = a[i + offset + p * 3] * rot3
a1na3imag = (a1 - a3) % MOD * IMAG
a[i + offset] = (a0 + a2 + a1 + a3) % MOD
a[i + offset + p] = (a0 + a2 - a1 - a3) % MOD
a[i + offset + p * 2] = (a0 - a2 + a1na3imag) % MOD
a[i + offset + p * 3] = (a0 - a2 - a1na3imag) % MOD
rot *= rate3[(~s & -~s).bit_length()]
rot %= MOD
le += 2
def butterfly_inv(a: list):
n = len(a)
h = (n - 1).bit_length()
le = h
while le:
if le == 1:
p = 1 << (h - le)
irot = 1
for s in range(1 << (le - 1)):
offset = s << (h - le + 1)
for i in range(p):
l = a[i + offset]
r = a[i + offset + p]
a[i + offset] = (l + r) % MOD
a[i + offset + p] = (l - r) * irot % MOD
irot *= irate2[(~s & -~s).bit_length()]
irot %= MOD
le -= 1
else:
p = 1 << (h - le)
irot = 1
for s in range(1 << (le - 2)):
irot2 = irot * irot % MOD
irot3 = irot2 * irot % MOD
offset = s << (h - le + 2)
for i in range(p):
a0 = a[i + offset]
a1 = a[i + offset + p]
a2 = a[i + offset + p * 2]
a3 = a[i + offset + p * 3]
a2na3iimag = (a2 - a3) * IIMAG % MOD
a[i + offset] = (a0 + a1 + a2 + a3) % MOD
a[i + offset + p] = (a0 - a1 + a2na3iimag) * irot % MOD
a[i + offset + p * 2] = (a0 + a1 - a2 - a3) * irot2 % MOD
a[i + offset + p * 3] = (a0 - a1 - a2na3iimag) * irot3 % MOD
irot *= irate3[(~s & -~s).bit_length()]
irot %= MOD
le -= 2
def intt(a):
if len(a) <= 1:
return
butterfly_inv(a)
iv = pow(len(a), MOD - 2, MOD)
for i, x in enumerate(a):
a[i] = x * iv % MOD
def multiply(s: list, t: list):
n = len(s)
m = len(t)
if min(n, m) <= 60:
a = [0] * (n + m - 1)
for i in range(n):
if i & 0b111 == 0:
for j in range(m):
a[i + j] += s[i] * t[j]
a[i + j] %= MOD
else:
for j in range(m):
a[i + j] += s[i] * t[j]
return [x % MOD for x in a]
a = s.copy()
b = t.copy()
z = 1 << (n + m - 2).bit_length()
a += [0] * (z - n)
b += [0] * (z - m)
butterfly(a)
butterfly(b)
for i in range(z):
a[i] *= b[i]
a[i] %= MOD
butterfly_inv(a)
a = a[: n + m - 1]
iz = pow(z, MOD - 2, MOD)
return [v * iz % MOD for v in a]
def pow2(s: list):
n = len(s)
l = (n << 1) - 1
if n <= 60:
a = [0] * l
for i, x in enumerate(s):
for j, y in enumerate(s):
a[i + j] += x * y
return [x % MOD for x in a]
z = 1 << (l - 1).bit_length()
a = s + [0] * (z - n)
butterfly(a)
for i, x in enumerate(a):
a[i] = x * x % MOD
butterfly_inv(a)
a[l:] = []
iz = pow(z, MOD - 2, MOD)
return [x * iz % MOD for x in a]
def shrink(a: list):
while a and not a[-1]:
a.pop()
def fps_add(a: list, b: list):
if len(a) < len(b):
res = b.copy()
for i, x in enumerate(a):
res[i] += x
else:
res = a.copy()
for i, x in enumerate(b):
res[i] += x
return [x - MOD if MOD <= x else x for x in res]
def fps_sub(a: list, b: list):
if len(a) < len(b):
res = b.copy()
for i, x in enumerate(a):
res[i] -= x
return [MOD - x if 0 < x else -x for x in res]
else:
res = a.copy()
for i, x in enumerate(b):
res[i] -= x
return [x if 0 <= x else x + MOD for x in res]
def fps_neg(a: list):
return [MOD - x if x else 0 for x in a]
def fps_div(a: list, b: list) -> list:
if len(a) < len(b):
return []
n = len(a) - len(b) + 1
cnt = 0
if len(b) > 64:
return multiply(a[::-1][:n], fps_inv(b[::-1], n))[:n][::-1]
f = a.copy()
g = b.copy()
while g and not g[-1]:
g.pop()
cnt += 1
coef = pow(g[-1], MOD - 2, MOD)
g = [x * coef % MOD for x in g]
deg = len(f) - len(g) + 1
lg = len(g)
res = [0] * deg
for i in reversed(range(deg)):
res[i] = x = f[i + lg - 1] % MOD
for j, y in enumerate(g):
f[i + j] -= x * y
return [x * coef % MOD for x in res] + [0] * cnt
def fps_mod(a: list, b: list) -> list:
res = fps_sub(a, multiply(fps_div(a, b), b))
while res and not res[-1]:
res.pop()
return res
def fps_divmod(a: list, b: list):
q = fps_div(a, b)
r = fps_sub(a, multiply(q, b))
while r and not r[-1]:
r.pop()
return q, r
def fps_eval(a: list, x: int) -> int:
r = 0
w = 1
for v in a:
r += w * v % MOD
w = w * x % MOD
return r % MOD
def fps_inv(a: list, deg: int = -1):
# assert(self[0] != 0)
if deg == -1:
deg = len(a)
res = [0] * deg
res[0] = pow(a[0], MOD - 2, MOD)
d = 1
iv = INV2
while d < deg:
d2 = d << 1
f = [0] * d2
fl = min(len(a), d2)
f[:fl] = a[:fl]
g = [0] * d2
g[:d] = res[:d]
butterfly(g)
butterfly(f)
for i in range(d2):
f[i] = f[i] * g[i] % MOD
butterfly_inv(f)
f[:d] = [0] * d
for i in range(d, d2):
f[i] = f[i] * iv % MOD
butterfly(f)
for i in range(d2):
f[i] = f[i] * g[i] % MOD
butterfly_inv(f)
for i in range(d, min(d2, deg)):
res[i] = (MOD - f[i]) * iv % MOD
d <<= 1
iv = iv * INV2 % MOD
return res
def fps_pow(a: list, k: int, deg=-1) -> list:
n = len(a)
if deg == -1:
deg = n
if k == 0:
if not deg:
return []
res = [0] * deg
res[0] = 1
return res
for i, x in enumerate(a):
if x:
iz = pow(x, MOD - 2, MOD)
res = [x * iz % MOD for x in a[i:]]
res = fps_log(res, deg)
res = [x * k % MOD for x in res]
res = fps_exp(res, deg)
coef = pow(x, k, MOD)
res = [0] * (i * k) + [x * coef % MOD for x in res]
if len(res) < deg:
return res + [0] * (deg - len(res))
return res[:deg]
if (i + 1) * k >= deg:
break
return [0] * deg
def fps_exp(a: list, deg: int = -1):
# assert a[0] == 0
if deg == -1:
deg = len(a)
inv = [0, 1]
def inplace_integral(f: list) -> list:
n = len(f)
while len(inv) <= n:
j, k = divmod(MOD, len(inv))
inv.append((-inv[k] * j) % MOD)
return [0] + [x * inv[i + 1] % MOD for i, x in enumerate(f)]
b = [1, (a[1] if 1 < len(a) else 0)]
c = [1]
z1 = []
z2 = [1, 1]
m = 2
while m < deg:
y = b + [0] * m
butterfly(y)
z1 = z2
z = [y[i] * p % MOD for i, p in enumerate(z1)]
intt(z)
z[: m >> 1] = [0] * (m >> 1)
butterfly(z)
for i, p in enumerate(z1):
z[i] = z[i] * (-p) % MOD
intt(z)
c[m >> 1 :] = z[m >> 1 :]
z2 = c + [0] * m
butterfly(z2)
tmp = min(len(a), m)
x = a[:tmp] + [0] * (m - tmp)
x = fps_diff(x)
x.append(0)
butterfly(x)
for i, p in enumerate(x):
x[i] = y[i] * p % MOD
intt(x)
for i, p in enumerate(b):
if not i:
continue
x[i - 1] -= p * i % MOD
x += [0] * m
for i in range(m - 1):
x[m + i], x[i] = x[i], 0
butterfly(x)
for i, p in enumerate(z2):
x[i] = x[i] * p % MOD
intt(x)
x.pop()
x = inplace_integral(x)
x[:m] = [0] * m
for i in range(m, min(len(a), m << 1)):
x[i] += a[i]
butterfly(x)
for i, p in enumerate(y):
x[i] = x[i] * p % MOD
intt(x)
b[m:] = x[m:]
m <<= 1
return b[:deg]
def fps_log(a: list, deg=-1) -> list:
# assert(a[0] == 1)
if deg == -1:
deg = len(a)
return fps_integral(multiply(fps_diff(a), fps_inv(a, deg))[: deg - 1])
def fps_integral(a: list):
n = len(a)
res = [0] * (n + 1)
if n:
res[1] = 1
for i in range(2, n + 1):
j, k = divmod(MOD, i)
res[i] = (-res[k] * j) % MOD
for i, x in enumerate(a):
res[i + 1] = res[i + 1] * x % MOD
return res
def fps_diff(a: list):
return [i * x % MOD for i, x in enumerate(a) if i]
def LinearRecurrence(n: int, p: list, q: list):
"""
[x^n]P(x)/Q(x)
"""
# assert len(p) < len(q)
shrink(q)
while n:
q2 = q[:]
for i in range(1, len(q2), 2):
q2[i] = (-q2[i]) % MOD
s = multiply(p, q2)
t = multiply(q, q2)
for i in range(n & 1, len(s), 2):
p[i >> 1] = s[i]
for i in range(0, len(t), 2):
q[i >> 1] = t[i]
n >>= 1
return p[0] * pow(q[0], -1, MOD) % MOD
def fps_compsite(f: list, g: list):
"""
g(f(x)) mod x^(n+1)
"""
# assert len(f) == len(g)
def trans_multiply(s, t):
n = len(s)
m = len(t)
l = 1 << (max(n, m) - 1).bit_length()
a = s + [0] * (l - n)
b = t + [0] * (l - m)
a = [a[0]] + [a[l - i] for i in range(1, l)]
butterfly(a)
butterfly(b)
iz = pow(l, MOD - 2, MOD)
for i, x in enumerate(b):
a[i] = a[i] * x % MOD * iz % MOD
butterfly_inv(a)
a = [a[0]] + [a[l - i] for i in range(1, l)]
return a[: n - m + 1]
n = len(f)
l = 1 << (n - 1).bit_length()
a = [MOD - x for x in f] + [0] * (2 * l - n)
b = g + [0] * (l - n)
def _inner(q, n, k):
if n == 1:
p = [0] * (2 * k)
p[0::2] = b[::-1]
return p
siz = 2 * n * k
r = [MOD - x if i & 1 else x for i, x in enumerate(q)]
qq = multiply(q, r)
qq.append(0)
for i in range(0, siz, 2):
qq[siz + i] = (qq[siz + i] + 2 * q[i]) % MOD
nq = [0] * siz
for j in range(2 * k):
for i in range(n >> 1):
nq[n * j + i] = qq[2 * n * j + 2 * i]
np = _inner(nq, n >> 1, k << 1)
pq = [0] * (2 * siz)
for j in range(2 * k):
for i in range(n >> 1):
pq[2 * n * j + 2 * i + 1] = np[n * j + i]
p = [pq[siz + i] for i in range(siz)]
pq.pop()
x = trans_multiply(pq, r)
p = [(p[i] + x[i]) % MOD for i in range(siz)]
return p
p = _inner(a, l, 1)
p = p[l - 1 :: -1]
return p[:n]
def fps_compsitional_inv(calc, deg):
"""
input
calc(g, d) = f(g(x)) mod x^d を計算する
fps_compsite よりも良い計算量のものが存在するならば書く
output
g(x) mod x^deg s.t. f(g(x)) = x
"""
c = deg.bit_length()
g = calc([0, 1], 2)
g[1] = pow(g[1], -1, MOD)
d = 2
for i in range(c):
d <<= 1
fg = calc(g, d + 1)
fdg = multiply(fps_diff(fg), fps_inv(fps_diff(g)))
fdg[d:] = []
fg[1] -= 1
g = fps_sub(g, multiply(fg, fps_inv(fdg)))
g[d:] = []
g[deg:] = []
return g
INVMOD = [1, 1]
def SubsetSum(d: list) -> list:
"""
prod ( 1 + x^i ) ^ d[i]
d[w] = 重さ w が d[w] 種類 1 個ずつある
r[w] = 重さが w になるような選び方
"""
n = len(d)
for i in range(len(INVMOD), n):
INVMOD.append(-INVMOD[MOD % i] * (MOD // i) % MOD)
res = [0] * n
sgn = [-1, 1]
for i in range(1, n):
if d[i]:
tmp = d[i] * i
for j in range(i, n, i):
res[j] += tmp * INVMOD[j] * sgn[(j // i) & 1] % MOD
res = fps_exp(res, n)
return res
def MultisetSum(d: list) -> list:
"""
prod ( 1 / ( 1 - x^i ) ) ^ d[i]
d[w] = 重さ w が d[w] 種類 inf 個ずつある
r[w] = 重さが w になるような選び方
"""
n = len(d)
for i in range(len(INVMOD), n):
INVMOD.append(-INVMOD[MOD % i] * (MOD // i) % MOD)
res = [0] * n
for i in range(1, n):
if d[i]:
tmp = d[i] * i
for j in range(i, n, i):
res[j] += tmp * INVMOD[j] % MOD
res = fps_exp(res, n)
return res
fac = [1, 1]
finv = [1, 1]
def tayler_shift(a: list, c: int) -> list:
global fac, finv
n = len(a)
l = len(fac)
fac += [0] * (n - l)
finv += [0] * (n - l)
for i in range(l, n):
fac[i] = fac[i - 1] * i % MOD
finv[n - 1] = pow(fac[n - 1], MOD - 2, MOD)
for i in reversed(range(l, n - 1)):
finv[i] = finv[i + 1] * (i + 1) % MOD
r = [x * fac[i] % MOD for i, x in enumerate(a)]
b = [0] * n
b[0] = 1
for i in range(1, n):
b[i] = b[i - 1] * c % MOD * finv[i] % MOD * fac[i - 1] % MOD
r.reverse()
res = multiply(r, b)[:n]
return [x * finv[i] % MOD for i, x in enumerate(reversed(res))]
def _fft2d(s: list[list]):
h, w = len(s), len(s[0])
for i in range(h):
butterfly(s[i])
buf = [0] * h
for j in range(w):
buf = [s[i][j] for i in range(h)]
butterfly(buf)
for i in range(h):
s[i][j] = buf[i]
def _ifft2d(s: list[list]):
h, w = len(s), len(s[0])
buf = [0] * h
for j in range(w):
buf = [s[i][j] for i in range(h)]
intt(buf)
for i in range(h):
s[i][j] = buf[i]
for i in range(h):
intt(s[i])
def multiply_2D(s: list[list], t: list[list]):
"""
not verify
"""
from copy import deepcopy
hs, ws = len(s), len(s[0])
ht, wt = len(t), len(t[0])
h = 1 << (hs + ht - 2).bit_length()
w = 1 << (ws + wt - 2).bit_length()
a = deepcopy(s)
b = deepcopy(t)
for i in range(hs):
a[i] += [0] * (w - ws)
for i in range(ht):
b[i] += [0] * (w - wt)
a += [[0] * w for i in range(h - hs)]
b += [[0] * w for i in range(h - ht)]
_fft2d(a)
_fft2d(b)
for i in range(h):
for j in range(w):
a[i][j] *= b[i][j]
a[i][j] %= MOD
_ifft2d(a)
a = a[: hs + ht - 1]
for i in range(hs + ht - 1):
a[i][ws + wt - 1 :] = []
return a
・Bostan-Mori法
# https://atcoder.jp/contests/tdpc/submissions/29624177
CONV = FFT(MOD)
def Bostan_Mori(P,Q,N):
"""
[x^n] P(x)/Q(x) を d^2 log N ないし d log d log N で求める
"""
if N==0:
return P[0]
Q2=[]
for i in range(len(Q)):
if i%2:Q2.append(-Q[i])
else:Q2.append(Q[i])
V=CONV.convolution(Q,Q2)[::2]
if N%2:return Bostan_Mori(CONV.convolution(P,Q2)[1::2],V,N//2)
else:return Bostan_Mori(CONV.convolution(P,Q2)[::2],V,N//2)
・階乗
def factorial(n):
F = [1]
for i in range(1, n+1):
F.append(F[-1]*i%MOD)
invF = [pow(F[-1], -1, MOD)]
for i in reversed(range(n)):
invF.append(invF[-1]*(i+1)%MOD)
invF = invF[::-1]
return F, invF
・グラフ ランダム生成
def gen_connected_graph(N, M, rng):
assert M >= N-1
edges = []
used = set()
# まず木を作る
for i in range(1, N):
p = rng.randint(0, i-1)
u, v = min(p, i), max(p, i)
edges.append((u, v))
used.add((u, v))
# 残りの辺をランダム追加
while len(edges) < M:
u = rng.randint(0, N-1)
v = rng.randint(0, N-1)
if u == v:
continue
u, v = min(u, v), max(u, v)
if (u, v) in used:
continue
edges.append((u, v))
used.add((u, v))
return edges
・UnionFind（左右を管理）
class UnionFind:
def __init__(self, n):
self.n = n
self.parent_size = [-1]*n
self.L = list(range(n))
self.R = list(range(n))
def leader(self, a):
if self.parent_size[a] < 0:
return a
self.parent_size[a] = self.leader(self.parent_size[a])
return self.parent_size[a]
def merge(self, a, b):
x, y = self.leader(a), self.leader(b)
if x == y:
return
if abs(self.parent_size[x]) < abs(self.parent_size[y]):
x, y = y, x
self.parent_size[x] += self.parent_size[y]
self.parent_size[y] = x
self.L[x] = min(self.L[x], self.L[y])
self.R[x] = max(self.R[x], self.R[y])
return
def left(self, n):
return self.L[self.leader(n)]
def right(self, n):
return self.R[self.leader(n)]
def same(self, a, b):
return self.leader(a) == self.leader(b)
def size(self, a):
return abs(self.parent_size[self.leader(a)])
def groups(self):
result = [[] for _ in range(self.n)]
for i in range(self.n):
result[self.leader(i)].append(i)
return [r for r in result if r != []]
・行列式
def det(A):
ans = 1
N = len(A)
sign = 1
for i in range(N):
pivot = i
while pivot < N and A[pivot][i] == 0:
pivot += 1
if pivot == N:
return 0
if pivot != i:
A[i], A[pivot] = A[pivot], A[i]
sign *= -1
inv = pow(A[i][i], -1, MOD)
for j in range(i+1, N):
factor = A[j][i]*inv%MOD
for k in range(i, N):
A[j][k] = (A[j][k]-factor*A[i][k])%MOD
ans *= A[i][i]
ans %= MOD
ans *= sign
ans %= MOD
return ans
・最小共通祖先（重み付き）
class LCA:
def __init__(self, G, root=0):
V = len(G)
self.bit_length = 1
while 1<<self.bit_length < V:
self.bit_length += 1
self.parent = [[-1]*V for _ in range(self.bit_length)]
self.depth = [-1]*V
self.depth2 = [-1]*V
self.bfs(G, root)
for i in range(self.bit_length-1):
for j in range(V):
if self.parent[i][j] != -1:
self.parent[i+1][j] = self.parent[i][self.parent[i][j]]
def bfs(self, G, root):
self.depth[root] = 0
que = deque()
que.append(root)
while que:
n = que.popleft()
for v, w in G[n]:
if self.depth[v] == -1:
self.depth[v] = self.depth[n]+1
self.depth2[v] = self.depth2[n]+w
self.parent[0][v] = n
que.append(v)
def lca(self, a, b):
if self.depth[a] < self.depth[b]:
a, b = b, a
for i in range(self.bit_length):
if (self.depth[a]-self.depth[b]) & 1<<i:
a = self.parent[i][a]
if a == b:
return a
for i in reversed(range(self.bit_length)):
if self.parent[i][a] != self.parent[i][b]:
a = self.parent[i][a]
b = self.parent[i][b]
return self.parent[0][a]
def dist(self, a, b):
return self.depth[a]+self.depth[b]-self.depth[self.lca(a, b)]*2
def dist2(self, a, b):
return self.depth2[a]+self.depth2[b]-self.depth2[self.lca(a, b)]*2
def is_ancestor(self, u, v):
return self.lca(u, v) == u
def kth_ancestor(self, n, k):
for i in range(self.bit_length):
if 1<<i & k:
n = self.parent[i][n]
if n == -1:
break
return n
def jump(self, u, v):
if u == v:
return u
if self.lca(u, v) == u:
return self.kth_ancestor(v, self.dist(u, v)-1)
else:
return self.parent[0][u]
def jump_k(self, u, v, k):
d = self.dist(u, v)
if d <= k:
return v
lca = self.lca(u, v)
if k <= self.depth[u]-self.depth[lca]:
return self.kth_ancestor(u, k)
else:
return self.kth_ancestor(v, d-k)
def on_path(self, u, v, x):
return self.dist(u, x)+self.dist(x, v) == self.dist(u, v)
def create_path(self, u, v, x):
if self.on_path(u, v, x):
return u, v
if self.on_path(u, x, v):
return u, x
if self.on_path(v, x, u):
return v, x
return -1, -1
・（重み付き）AuxiliaryTree
class AuxiliaryTree:
def __init__(self, N, G):
self.N = N
self.G = G
self.IN = [0]*N
self.OUT = [0]*N
self.depth = [0]*N
self.depth2 = [0]*N
self.E = []
self.dfs(0, -1, 0, 0)
self.L = len(self.E)
self.lg = [0]*(self.L+1)
self.make_sparse_table()
@bootstrap
def dfs(self, n, p, d, d2):
self.depth[n] = d
self.depth2[n] = d2
self.IN[n] = len(self.E)
self.E.append(n)
for v, w in self.G[n]:
if v == p:
continue
yield self.dfs(v, n, d+1, d2+w)
self.E.append(n)
self.OUT[n] = len(self.E)
self.E.append(n)
yield
def make_sparse_table(self):
for i in range(2, self.L+1):
self.lg[i] = self.lg[i>>1]+1
self.st = [[self.L]*(self.L-(1<<i)+1) for i in range(self.lg[self.L]+1)]
self.st[0] = self.E[:]
b = 1
for i in range(self.lg[self.L]):
for j in range(self.L-(b<<1)+1):
self.st[i+1][j] = (self.st[i][j] if self.depth[self.st[i][j]] <= self.depth[self.st[i][j+b]] else self.st[i][j+b])
b <<= 1
def lca(self, u, v):
x, y = self.IN[u], self.IN[v]
l = self.lg[y-x+1]
return self.st[l][x] if self.depth[self.st[l][x]] <= self.depth[self.st[l][y-(1<<l)+1]] else self.st[l][y-(1<<l)+1]
def query(self, v):
nG = defaultdict(list)
V = v[:]
V.sort(key=self.IN.__getitem__)
K = len(V)
stack = [V[0]]
for i in range(K-1):
w = self.lca(V[i], V[i+1])
if w != V[i]:
last = stack.pop()
while stack and self.depth[w] < self.depth[stack[-1]]:
d = abs(self.depth[stack[-1]]-self.depth[last])
d2 = abs(self.depth2[stack[-1]]-self.depth2[last])
nG[stack[-1]].append((last, d, d2))
nG[last].append((stack[-1], d, d2))
last = stack.pop()
if not stack or stack[-1] != w:
stack.append(w)
V.append(w)
d = abs(self.depth[w]-self.depth[last])
d2 = abs(self.depth2[w]-self.depth2[last])
nG[w].append((last, d, d2))
nG[last].append((w, d, d2))
stack.append(V[i+1])
for i in range(len(stack)-1):
d = abs(self.depth[stack[i]]-self.depth[stack[i+1]])
d2 = abs(self.depth2[stack[i]]-self.depth2[stack[i+1]])
nG[stack[i]].append((stack[i+1], d, d2))
nG[stack[i+1]].append((stack[i], d, d2))
return nG, stack[0]
・Aho-Corasick
class AhoCorasick:
def __init__(self, type):
self.next = [[-1]*26]
self.link = [-1]
self.out = [[]]
self.size = 1
self.base = ord("a") if type == 0 else ord("A")
def code(self, s):
return ord(s)-self.base
def add_word(self, word, idx):
v = 0
for c in word:
if self.next[v][self.code(c)] == -1:
self.next[v][self.code(c)] = self.size
self.next.append([-1]*26)
self.link.append(0)
self.out.append([])
self.size += 1
v = self.next[v][self.code(c)]
self.out[v].append(idx)
def build(self):
que = deque()
for i in range(26):
if self.next[0][i] != -1:
self.link[self.next[0][i]] = 0
que.append(self.next[0][i])
while que:
n = que.popleft()
for i in range(26):
if self.next[n][i] != -1:
f = self.link[n]
while f != -1 and self.next[f][i] == -1:
f = self.link[f]
if f == -1:
self.link[self.next[n][i]] = 0
else:
self.link[self.next[n][i]] = self.next[f][i]
self.out[self.next[n][i]].extend(self.out[self.link[self.next[n][i]]])
que.append(self.next[n][i])
def match(self, text):
res = []
n = 0
for i, c in enumerate(text):
while n != 0 and self.next[n][self.code(c)] == -1:
n = self.link[n]
if self.next[n][self.code(c)] != -1:
n = self.next[n][self.code(c)]
for idx in self.out[n]:
res.append((i, idx))
return res
def go(self, idx, s):
while 1 <= idx and self.next[idx][self.code(s)] == -1:
idx = self.link[idx]
return self.next[idx][self.code(s)] if self.next[idx][self.code(s)] != -1 else 0
・BIT（MOD）
class BIT:
def __init__(self, A):
self.size = len(A)
self.bit = [0]*(len(A)+1)
for i in range(len(A)):
self.add(i, A[i])
def sum(self, i):
i += 1
ans = 0
while i > 0:
ans += self.bit[i]
ans %= MOD
i -= -i&i
return ans
def query(self, l, r):
if l == 0:
return self.sum(r-1)
else:
return (self.sum(r-1)-self.sum(l-1))%MOD
def add(self, i, x):
i += 1
while i <= self.size:
self.bit[i] += x
self.bit[i] %= MOD
i += -i&i
・オフラインrangefreq
def offline_range_freq_to(A, query):
N = len(A)
Q = len(query)
A = sorted(enumerate(A), key=lambda x:x[1])
query = sorted(enumerate(query), key=lambda x:x[1][2])
F = BIT([0]*N)
ans = [-1]*Q
idx = 0
for qidx, (l, r, x) in query:
while idx < N and A[idx][1] <= x:
F.add(A[idx][0], 1)
idx += 1
ans[qidx] = F.query(l, r+1)
return ans
def offline_range_freq_from(A, query):
N = len(A)
Q = len(query)
A = sorted(enumerate(A), key=lambda x:x[1], reverse=True)
query = sorted(enumerate(query), key=lambda x:x[1][2], reverse=True)
F = BIT([0]*N)
ans = [-1]*Q
idx = 0
for qidx, (l, r, x) in query:
while idx < N and x <= A[idx][1]:
F.add(A[idx][0], 1)
idx += 1
ans[qidx] = F.query(l, r+1)
return ans
・Codonテンプレート
#generatorに__getitem__, __contains__を定義
@extend
class Generator:
def __getitem__(self: Generator[T], _: int) -> T:
if self.done(): raise StopIteration()
return self.next()
def __getitem__(self: Generator[T], key: slice) -> list[T]:
assert key.stop is None, (
'''本拡張では、末尾以外でのアンパッキングはできません。
例として、 N, *A = generator には対応しますが *A, N = generator は非対応です。
右辺の generator を list(generator) と書き換えてみてください。''')
return list(self)
def __contains__(self: Generator[T], key: T) -> bool:
return key in list(self)
#int同士の除算結果をPythonの負の無限大丸めに合わせる
@extend
class int:
@pure
@llvm
def _floordiv_int_int(self: int, other: int) -> int:
%0 = sdiv i64 %self, %other
ret i64 %0
@overload
def __floordiv__(self, other: int):
d = self._floordiv_int_int(other)
m = self - d * other
if m and ((other ^ m) < 0):
d -= 1
return d
@pure
@llvm
def _mod_int_int(self: int, other: int) -> int:
%0 = srem i64 %self, %other
ret i64 %0
@overload
def __mod__(self, other: int) -> int:
m = self._mod_int_int(other)
if m and ((other ^ m) < 0):
m += other
return m
#int.bit_length, int.bit_countに対応
@extend
class int:
def bit_length(self):
return 64 - abs(self).__ctlz__()
def bit_count(self):
return abs(self).__ctpop__()
#int hash値をSplitMix64で変更する
#Reference: https://prng.di.unimi.it/splitmix64.c
@extend
class int:
def __hash__(self) -> int:
z: UInt[64] = UInt[64](self) + UInt[64](0x9e3779b97f4a7c15)
z = (z ^ (z >> UInt[64](30))) * UInt[64](0xbf58476d1ce4e5b9)
z = (z ^ (z >> UInt[64](27))) * UInt[64](0x94d049bb133111eb)
return int(z ^ (z >> UInt[64](31)))
#floatの出力桁数を15桁に増やす
@extend
class float:
def __str__(self): return f'{self:15f}'
#巨大mod時のオーバーフローを回避 pow(base, -1, mod)に対応
def _extended_pow():
_builtin_pow = pow
def _codon_pow(base, exp):
return _builtin_pow(base, exp)
@overload
def _codon_pow(base: int, exp: int, mod: int) -> int:
'''
codon用に pow(base, exp, mod) を拡張した関数です。
1. (abs(mod) - 1) ** 2 >= 1 << 63 の場合に発生していたオーバーフローを回避しました。
2. pow(base: int, exp: 負整数, mod: int) による逆元計算に対応しました。
返り値の符号は mod の符号に一致します。
いずれかの引数に INF_MIN := -1 << 63 を渡した場合の動作は未定義です。
'''
if mod == 0:
raise ValueError('pow() 3rd argument cannot be 0')
if mod == 1 or mod == -1:
return 0
if exp < 0: #拡張ユークリッドの互除法
a, b, x, y = base, mod, 1, 0
while b:
q = a // b
a, b, x, y = b, a - q * b, y, x - q * y
if a != 1 and a != -1:
raise ValueError('base is not invertible for the given modulus')
b128, m128 = Int[128](x), Int[128](mod)
if a == -1:
b128 = - b128
exp = - exp
else:
b128, m128 = Int[128](base), Int[128](mod)
v128 = Int[128](1)
while exp:
if exp & 1 == 1:
v128 = v128 * b128 % m128
b128 = b128 * b128 % m128
exp >>= 1
v = int(v128)
return v + mod if v != 0 and (0 < v) != (0 < mod) else v
return _codon_pow
pow = _extended_pow()
・スライド最小値（最大値）
class MonotonicQueue:
def __init__(self, A, isMIN=True):
self.N = len(A)
self.A = A
self.isMIN = isMIN
self.que = deque()
self.left = 0
self.right = 0
def _cmp(self, a, b):
return a >= b if self.isMIN else a <= b
def move_right(self):
if self.right == self.N: return False
while self.que and self._cmp(self.que[-1][0], self.A[self.right]):
self.que.pop()
self.que.append((self.A[self.right], self.right))
self.right += 1
return True
def move_left(self):
if self.left == self.right: return False
if self.que[0][1] == self.left:
self.que.popleft()
self.left += 1
return True
def get(self):
return self.que[0][0] if self.que else None
・オイラーグラフ判定
def isEulerGraph(G, isDirected = False):
N = len(G)
if not isDirected:
cnt = [0]*N
UF = UnionFind(N)
for n in range(N):
for v in G[n]:
cnt[n] += 1
UF.merge(n, v)
odd = sum(cnt[i]%2 == 1 for i in range(N))
cntE = sum(1 <= cnt[i] for i in range(N))
if odd == 0:
if 1 <= cntE:
for i in range(N):
if 1 <= cnt[i]:
if UF.size(i) == cntE:
return True, True, i, -1
else:
return False, False, -1, -1
else:
return True, True, -1, -1
elif odd == 2:
l, r = -1, -1
for i in range(N):
if cnt[i]%2 == 1:
if l == -1:
l = i
else:
r = i
break
if UF.size(l) == cntE:
return True, False, l, r
else:
return False, False, -1, -1
else:
return False, False, -1, -1
else:
IN = [0]*N
OUT = [0]*N
UF = UnionFind(N)
for n in range(N):
for v in G[n]:
OUT[n] += 1
IN[v] += 1
UF.merge(n, v)
s, g = -1, -1
m = -1
cntE = sum(1 <= IN[i]+OUT[i] for i in range(N))
for i in range(N):
if IN[i]+1 == OUT[i]:
if s == -1:
s = i
else:
return False, False, -1, -1
elif OUT[i]+1 == IN[i]:
if g == -1:
g = i
else:
return False, False, -1, -1
elif IN[i] != OUT[i]:
return False, False, -1, -1
if 1 <= IN[i]+OUT[i] and m == -1:
m = i
if m != -1 and UF.size(m) != cntE:
return False, False, -1, -1
if s == g == -1:
return True, True, m, -1
elif s != -1 and g != -1:
return True, False, s, g
else:
return False, False, -1, -1
・二項係数の区間和
class rangeBinomial:
def __init__(self, N, L, R):
self.N = N
self.L = L
self.R = R
self.val = 0
for i in range(L, R+1):
self.val += cp.C(N, i)
self.val %= MOD
self.half = pow(2, -1, MOD)
def add(self):
self.val *= 2
self.val %= MOD
self.val += cp.C(self.N, self.L-1)-cp.C(self.N, self.R)
self.val %= MOD
self.N += 1
return True
def sub(self):
if self.N == 0:
return False
self.N -= 1
self.val += cp.C(self.N, self.R)-cp.C(self.N, self.L-1)
self.val %= MOD
self.val *= self.half
self.val %= MOD
return True
def move_ll(self):
if self.L == 0:
return False
self.L -= 1
self.val += cp.C(self.N, self.L)
self.val %= MOD
return True
def move_lr(self):
if self.L == self.R:
return False
self.val -= cp.C(self.N, self.L)
self.val %= MOD
self.L += 1
return True
def move_rr(self):
self.R += 1
self.val += cp.C(self.N, self.R)
self.val %= MOD
return True
def move_rl(self):
if self.L == self.R:
return False
self.val -= cp.C(self.N, self.R)
self.val %= MOD
self.R -= 1
return True
def get(self):
return self.val
・円の交点
def circle_intersections(x1, y1, r1, x2, y2, r2):
d = distance(x1, y1, x2, y2)
dx = x2 - x1
dy = y2 - y1
# 交点なし
if d > r1 + r2 or d < abs(r1 - r2) or d == 0:
return []
a = (r1*r1 - r2*r2 + d*d) / (2*d)
h_sq = r1*r1 - a*a
if h_sq < 0:
h_sq = 0
h = h_sq**0.5
x3 = x1 + a * dx / d
y3 = y1 + a * dy / d
rx = -dy * (h / d)
ry = dx * (h / d)
return [(x3 + rx, y3 + ry), (x3 - rx, y3 - ry)]
・2-SAT
class TwoSAT:
def __init__(self, N):
self.N = N
self.edge = []
self.solution = [False]*N
self.solved = False
def add_constraint(self, u, f, v, g):
self.edge.append((u+self.N*f, v+self.N*g))
def add_clause(self, u, f, v, g):
self.add_constraint(u, f^True, v, g)
self.add_constraint(v, g^True, u, f)
def solve(self):
SCC = scc(self.N*2, self.edge)
order = [-1]*(self.N*2)
for i, s in enumerate(SCC):
for n in s:
order[n] = i
for i in range(self.N):
if order[i] == order[i+self.N]:
return False
if order[i] > order[i+self.N]:
self.solution[i] = False
else:
self.solution[i] = True
self.solved = True
return True
def result(self):
return self.solution if self.solved else None
・2-SAT（密グラフ）
class TwoSAT:
def __init__(self, N, M):
self.N = N
self.M = M
self.edge = []
self.solution = [False]*self.N
self.cnt = 0
self.solved = False
def add_constraint(self, u, f, v, g):
self.edge.append((u+(self.N+self.M)*f, v+(self.N+self.M)*g))
def add_clause(self, u, f, v, g):
self.add_constraint(u, f^True, v, g)
self.add_constraint(v, g^True, u, f)
def add_at_most_one(self, A):
for i in range(len(A)):
self.add_clause(A[i][0], A[i][1], self.N+self.cnt+i, True)
if i+1 < len(A):
self.add_clause(self.N+self.cnt+i, False, self.N+self.cnt+i+1, True)
self.add_clause(self.N+self.cnt+i, False, A[i+1][0], A[i+1][1])
self.cnt += len(A)
def solve(self):
SCC = scc((self.N+self.M)*2, self.edge)
order = [-1]*((self.N+self.M)*2)
for i, s in enumerate(SCC):
for n in s:
order[n] = i
for i in range(self.N):
if order[i] == order[i+self.N+self.M]:
return False
if order[i] > order[i+self.N+self.M]:
self.solution[i] = False
else:
self.solution[i] = True
self.solved = True
return True
def result(self):
return self.solution[:self.N] if self.solved else None
・Slope-Trick
from heapq import heappush, heappop
class SlopeTrick:
def __init__(self):
self.min_f = 0
self.L = []
self.R = []
self.add_l = 0
self.add_r = 0
def push_R(self, a):
heappush(self.R, a-self.add_r)
def top_R(self):
return self.R[0]+self.add_r if self.R else INF
def pop_R(self):
val = self.top_R()
if self.R: heappop(self.R)
return val
def push_L(self, a):
heappush(self.L, -(a-self.add_l))
def top_L(self):
return -self.L[0]+self.add_l if self.L else -INF
def pop_L(self):
val = self.top_L()
if self.L: heappop(self.L)
return val
def size(self):
return len(self.L)+len(self.R)
def query(self):
return self.top_L(), self.top_R(), self.min_f
def add_all(self, a):
self.min_f += a
def add_x_minus_a(self, a):
self.min_f += max(self.top_L()-a, 0)
self.push_L(a)
self.push_R(self.pop_L())
def add_a_minus_x(self, a):
self.min_f += max(a-self.top_R(), 0)
self.push_R(a)
self.push_L(self.pop_R())
def add_abs(self, a):
self.add_x_minus_a(a)
self.add_a_minus_x(a)
def clear_right(self):
self.R = []
def clear_left(self):
self.L = []
def shift2(self, a, b):
self.add_l += a
self.add_r += b
def shift(self, a):
self.shift2(a, a)
def get(self, x):
ret = self.min_f
for l in self.L:
n = -l+self.add_l
ret += max(n-x, 0)
for r in self.R:
n = r+self.add_r
ret += max(x-n, 0)
return ret
def merge(self, st):
if self.size() < st.size():
self.L, st.L = st.L, self.L
self.R, st.R = st.R, self.R
self.add_l, st.add_l = st.add_l, self.add_l
self.add_r, st.add_r = st.add_r, self.add_r
self.min_f, st.min_f = st.min_f, self.min_f
while st.R:
self.add_x_minus_a(st.pop_R())
while st.L:
self.add_a_minus_x(st.pop_L())
self.min_f += st.min_f
・monotone minima
# select(i, j, k) AijとAikでAikを選ぶならTrue
def monotone_minima(H, W, select):
def solve(row):
L = len(row)
if L == 0: return []
row2 = [row[i] for i in range(L) if i%2 == 1]
ans2 = solve(row2)
ans = [0]*L
for i in range(len(ans2)):
ans[i*2+1] = ans2[i]
idx = 0
for i in range(0, L, 2):
ans[i] = idx
end = ans[i+1] if i+1 < L else W-1
while idx != end:
idx += 1
if select(row[i], ans[i], idx): ans[i] = idx
return ans
return solve(list(range(H)))
・最大値（最小値）Top2
class Top2:
def __init__(self):
self.best1 = (-INF, -1)
self.best2 = (-INF, -1)
def add(self, val, genre):
b1v, b1g = self.best1
b2v, b2g = self.best2
if genre == b1g:
if val > b1v:
self.best1 = (val, genre)
else:
if val > b1v:
self.best2 = self.best1
self.best1 = (val, genre)
elif val > b2v:
self.best2 = (val, genre)
def get_exclude(self, genre):
if self.best1[1] != genre:
return self.best1[0]
else:
return self.best2[0]
・LCA（Sparse Table）
class LCA:
def __init__(self, G, root=0):
self.G = G
self.N = len(G)
self.A = []
self.IN = [0]*self.N
self.depth = [0]*self.N
self.dfs(root, -1, 0)
self.L = len(self.A)
self.log = [0]*(self.L + 1)
for i in range(2, self.L+1):
self.log[i] = self.log[i >> 1] + 1
self.sparse = [None]*(self.log[self.L] + 1)
self.sparse[0] = self.A
b = 1
for i in range(self.log[self.L]):
self.sparse[i+1] = [p if self.depth[p] <= self.depth[q] else q for p, q in zip(self.sparse[i], self.sparse[i][b:])]
b <<= 1
@bootstrap
def dfs(self, n, p, d):
self.depth[n] = d
self.IN[n] = len(self.A)
self.A.append(n)
for v in self.G[n]:
if v == p:
continue
yield self.dfs(v, n, d+1)
self.A.append(n)
yield
def lca(self, u, v):
l = self.IN[u]
r = self.IN[v]
if l > r:
l, r = r, l
k = self.log[r-l+1]
a = self.sparse[k][l]
b = self.sparse[k][r-(1<<k)+1]
return a if self.depth[a] <= self.depth[b] else b
def dist(self, a, b):
return self.depth[a]+self.depth[b]-self.depth[self.lca(a, b)]*2
・XOR基底
class XORBasis:
def __init__(self, A):
self.A = A
self.base = []
self.mask = []
self.IDX = []
self.dependent = -1
for i, a in enumerate(self.A):
n = a
xor = 1<<len(self.base)
for j, b in enumerate(self.base):
if n^b < n:
n ^= b
xor ^= self.mask[j]
if n:
self.IDX.append(i)
self.base.append(n)
self.mask.append(xor)
elif self.dependent == -1:
self.dependent = i
if len(self.base) == 0:
return
pairs = sorted(zip(self.base, self.mask), key=lambda x:x[0], reverse=True)
self.base, self.mask = map(list, zip(*pairs))
for i in range(1, len(self.base)):
for j in range(i):
if self.base[j]^self.base[i] < self.base[j]:
self.base[j] ^= self.base[i]
self.mask[j] ^= self.mask[i]
def can_make(self, x):
for b in self.base:
if 1<<(b.bit_length()-1) & x:
x ^= b
return x == 0
def can_make_nonemptyzero(self):
return self.dependent != -1
def get_indices(self, x):
xor = 0
for i, b in enumerate(self.base):
if 1<<(b.bit_length()-1) & x:
x ^= b
xor ^= self.mask[i]
if x:
return None
ans = []
for i in range(len(self.base)):
if 1<<i & xor:
ans.append(self.IDX[i])
return ans
def get_indices_nonemptyzero(self):
if not self.can_make_nonemptyzero():
return None
return sorted(self.get_indices(self.A[self.dependent])+[self.dependent])
def get_max(self, x = 0):
for b in self.base:
x = max(x, x^b)
return x
def get_min(self, x = 0):
for b in self.base:
x = min(x, x^b)
return x
def kth_min(self, k):
if k < 0 or 1<<len(self.base) < k:
return -1
ans = 0
for i, b in enumerate(self.base):
if 1<<(len(self.base)-1-i) & k:
ans ^= b
return ans
def kth_max(self, k):
return self.kth_min((1<<len(self.base))-k)
・XOR畳み込み
def FWHT(A, inverse=False):
N = len(A)
H = 1
while H < N:
for i in range(0, N, H*2):
for j in range(i, i+H):
x = A[j]
y = A[j+H]
A[j] = (x+y)%MOD
A[j+H] = (x-y)%MOD
H *= 2
if inverse:
inv = pow(N, -1, MOD)
for i in range(N):
A[i] *= inv
A[i] %= MOD
def xor_convolution(a, b):
A = a[:]
B = b[:]
N = 1
while N < max(len(A), len(B)):
N *= 2
A += [0]*(N-len(A))
B += [0]*(N-len(B))
FWHT(A)
FWHT(B)
for i in range(N):
A[i] *= B[i]
A[i] %= MOD
FWHT(A, inverse=True)
return A
・ランダムテスト
import subprocess
import sys
from random import randrange, shuffle
# 1.ファイル名を書き換える
SOL = ".py"
NAIVE = "_naive.py"
TEST_COUNT = 100
TIMEOUT_SECOND = 2
def generate():
# 2.入力を作成する
lines = []
return "\n".join(lines)+"\n"
def prepare(filename):
"""
実行するコマンドを返す。
Pythonならそのまま。
C++なら先にコンパイルする。
"""
if filename.endswith(".py"):
return [sys.executable, filename]
if filename.endswith(".cpp"):
exe = filename[:-4] + ".exe"
result = subprocess.run(
[
"g++",
filename,
"-std=c++20",
"-O2",
"-o",
exe,
],
text=True,
capture_output=True,
)
if result.returncode != 0:
print(f"{filename} のコンパイルに失敗")
print(result.stderr)
exit()
return [exe]
raise ValueError(f"対応していないファイル形式: {filename}")
def run(command, test):
try:
result = subprocess.run(
command,
input=test,
text=True,
capture_output=True,
timeout=TIMEOUT_SECOND,
)
except subprocess.TimeoutExpired:
print("TLE!")
print("command:", command)
print("===== input =====")
print(test, end="")
exit()
if result.returncode != 0:
print("RE!")
print("command:", command)
print("===== input =====")
print(test, end="")
print("===== stderr =====")
print(result.stderr)
exit()
return result.stdout.strip()
sol_command = prepare(SOL)
naive_command = prepare(NAIVE)
for t in range(TEST_COUNT):
test = generate()
ans1 = run(sol_command, test)
ans2 = run(naive_command, test)
if ans1 != ans2:
print("WA")
print("===== input =====")
print(test, end="")
print("===== solution =====")
print(ans1)
print("===== naive =====")
print(ans2)
with open("failed.txt", "w") as f:
f.write(test)
break
else:
print("All tests passed!")
・ランダムテスト（小数誤差許容）
import subprocess
import sys
import math
from random import randrange, shuffle
# 1.ファイル名を書き換える
SOL = ".py"
NAIVE = "_naive.py"
TEST_COUNT = 100
TIMEOUT_SECOND = 2
# 2.許容誤差を設定する
ABS_EPS = 1e-6
REL_EPS = 1e-6
def generate():
# 3.入力を作成する
lines = []
return "\n".join(lines)+"\n"
def prepare(filename):
"""
実行するコマンドを返す。
Pythonならそのまま。
C++なら先にコンパイルする。
"""
if filename.endswith(".py"):
return [sys.executable, filename]
if filename.endswith(".cpp"):
exe = filename[:-4] + ".exe"
result = subprocess.run(
[
"g++",
filename,
"-std=c++20",
"-O2",
"-o",
exe,
],
text=True,
capture_output=True,
)
if result.returncode != 0:
print(f"{filename} のコンパイルに失敗")
print(result.stderr)
exit()
return [exe]
raise ValueError(f"対応していないファイル形式: {filename}")
def run(command, test):
try:
result = subprocess.run(
command,
input=test,
text=True,
capture_output=True,
timeout=TIMEOUT_SECOND,
)
except subprocess.TimeoutExpired:
print("TLE!")
print("command:", command)
print("===== input =====")
print(test, end="")
exit()
if result.returncode != 0:
print("RE!")
print("command:", command)
print("===== input =====")
print(test, end="")
print("===== stderr =====")
print(result.stderr)
exit()
return result.stdout.strip()
def compare(ans1, ans2):
"""
空白区切りで比較する。
数値なら誤差を許容。
数値でないトークンは完全一致。
"""
A = ans1.split()
B = ans2.split()
if len(A) != len(B):
return False, f"出力トークン数が違う: {len(A)} != {len(B)}"
for i, (a, b) in enumerate(zip(A, B)):
try:
x = float(a)
y = float(b)
if not math.isfinite(x) or not math.isfinite(y):
return False, f"{i} 番目に非有限値がある: {a}, {b}"
if not math.isclose(
x,
y,
rel_tol=REL_EPS,
abs_tol=ABS_EPS,
):
return False, (
f"{i} 番目が誤差範囲外: "
f"{a} != {b}, diff = {abs(x-y)}"
)
except ValueError:
# 数値でなければ文字列として比較
if a != b:
return False, f"{i} 番目が違う: {a} != {b}"
return True, ""
sol_command = prepare(SOL)
naive_command = prepare(NAIVE)
for t in range(TEST_COUNT):
test = generate()
ans1 = run(sol_command, test)
ans2 = run(naive_command, test)
ok, reason = compare(ans1, ans2)
if not ok:
print("WA")
print("===== input =====")
print(test, end="")
print("===== solution =====")
print(ans1)
print("===== naive =====")
print(ans2)
print("===== reason =====")
print(reason)
with open("failed.txt", "w") as f:
f.write(test)
break
else:
print("All tests passed!")
・ランダムテスト（スペシャルジャッジ）
import subprocess
import sys
from random import randrange, shuffle
# 1.ファイル名を書き換える
SOL = ".py"
TEST_COUNT = 100
TIMEOUT_SECOND = 2
def generate():
# 2.入力を作成する
lines = []
return "\n".join(lines)+"\n"
# 3.解答が正しいか判定するコードを書く
def check(test, output):
"""
test : generate() で作った入力
output : SOL が出力した内容
正しければ
return True, ""
間違っていれば
return False, "間違っている理由"
"""
test = test.splitlines()
output = output.splitlines()
return True, ""
def prepare(filename):
"""
実行するコマンドを返す。
Pythonならそのまま。
C++なら先にコンパイルする。
"""
if filename.endswith(".py"):
return [sys.executable, filename]
if filename.endswith(".cpp"):
exe = filename[:-4] + ".exe"
result = subprocess.run(
[
"g++",
filename,
"-std=c++20",
"-O2",
"-o",
exe,
],
text=True,
capture_output=True,
)
if result.returncode != 0:
print(f"{filename} のコンパイルに失敗")
print(result.stderr)
exit()
return [exe]
raise ValueError(f"対応していないファイル形式: {filename}")
def run(command, test):
try:
result = subprocess.run(
command,
input=test,
text=True,
capture_output=True,
timeout=TIMEOUT_SECOND,
)
except subprocess.TimeoutExpired:
print("TLE!")
print("command:", command)
print("===== input =====")
print(test, end="")
exit()
if result.returncode != 0:
print("RE!")
print("command:", command)
print("===== input =====")
print(test, end="")
print("===== stderr =====")
print(result.stderr)
exit()
return result.stdout.strip()
sol_command = prepare(SOL)
for t in range(TEST_COUNT):
test = generate()
ans = run(sol_command, test)
try:
ok, reason = check(test, ans)
except Exception as e:
print("Checker Error!")
print("===== input =====")
print(test, end="")
print("===== output =====")
print(ans)
print("===== checker error =====")
print(repr(e))
break
if not ok:
print("WA")
print("===== input =====")
print(test, end="")
print("===== solution =====")
print(ans)
print("===== reason =====")
print(reason)
with open("failed.txt", "w") as f:
f.write(test)
break
else:
print("All tests passed!")
・ランダムテスト（インタラクティブ）
import subprocess
import sys
import threading
import queue
from random import randrange, shuffle
# 1.ファイル名を書き換える
SOL = ".py"
TEST_COUNT = 100
TIMEOUT_SECOND = 2
# 2.ジャッジが持つ秘密の情報を生成する。
def generate():
"""
普通のランテスと違って、
必ずしも文字列を返す必要はない。
例:
N = randrange(1, 101)
X = randrange(1, N+1)
return N, X
"""
return None
# 3.インタラクティブジャッジを書く。
def judge(io, case):
"""
io.send(s)
解答側に1行送る
io.recv()
解答側から1行受け取る
正解:
return True, ""
不正解:
return False, "理由"
"""
# ==========================================
# 例:
#
# N, X = case
#
# 最初にNを通知
# io.send(str(N))
#
# query_count = 0
#
# while True:
# line = io.recv()
# tokens = line.split()
#
# if len(tokens) == 2 and tokens[0] == "?":
# query_count += 1
#
# if query_count > 20:
# return False, "質問回数オーバー"
#
# x = int(tokens[1])
#
# if not (1 <= x <= N):
# return False, "質問が範囲外"
#
# if X <= x:
# io.send("Yes")
# else:
# io.send("No")
#
# elif len(tokens) == 2 and tokens[0] == "!":
# answer = int(tokens[1])
#
# if answer == X:
# return True, ""
# else:
# return False, f"答えが違う: {answer} != {X}"
#
# else:
# return False, f"不正な出力: {line}"
# ==========================================
return True, ""
def prepare(filename):
"""
実行するコマンドを返す。
Pythonならそのまま。
C++なら先にコンパイルする。
"""
if filename.endswith(".py"):
return [sys.executable, filename]
if filename.endswith(".cpp"):
exe = filename[:-4] + ".exe"
result = subprocess.run(
[
"g++",
filename,
"-std=c++20",
"-O2",
"-o",
exe,
],
text=True,
capture_output=True,
)
if result.returncode != 0:
print(f"{filename} のコンパイルに失敗")
print(result.stderr)
exit()
return [exe]
raise ValueError(f"対応していないファイル形式: {filename}")
class InteractiveProcess:
def __init__(self, command):
self.proc = subprocess.Popen(
command,
stdin=subprocess.PIPE,
stdout=subprocess.PIPE,
stderr=subprocess.PIPE,
text=True,
bufsize=1,
)
self.stdout_queue = queue.Queue()
self.stderr_lines = []
self.transcript = []
self.stdout_thread = threading.Thread(
target=self._read_stdout,
daemon=True,
)
self.stdout_thread.start()
self.stderr_thread = threading.Thread(
target=self._read_stderr,
daemon=True,
)
self.stderr_thread.start()
def _read_stdout(self):
for line in self.proc.stdout:
self.stdout_queue.put(line.rstrip("\r\n"))
# EOF
self.stdout_queue.put(None)
def _read_stderr(self):
for line in self.proc.stderr:
self.stderr_lines.append(line)
def send(self, s):
"""
ジャッジ → 解答
"""
if self.proc.poll() is not None:
raise RuntimeError(
f"解答プログラムが途中で終了した "
f"(returncode={self.proc.returncode})"
)
s = str(s)
self.transcript.append(("Judge", s))
try:
self.proc.stdin.write(s + "\n")
self.proc.stdin.flush()
except BrokenPipeError:
raise RuntimeError("解答プログラムが入力を受け取る前に終了した")
def recv(self):
"""
解答 → ジャッジ
"""
try:
line = self.stdout_queue.get(
timeout=TIMEOUT_SECOND
)
except queue.Empty:
raise TimeoutError(
f"{TIMEOUT_SECOND} 秒以内に応答がなかった"
)
if line is None:
returncode = self.proc.poll()
raise RuntimeError(
f"解答プログラムが途中で終了した "
f"(returncode={returncode})"
)
self.transcript.append(("Solution", line))
return line
def finish(self):
"""
正解判定後、解答プログラムが正常終了するか確認。
"""
if self.proc.stdin and not self.proc.stdin.closed:
self.proc.stdin.close()
try:
self.proc.wait(timeout=TIMEOUT_SECOND)
except subprocess.TimeoutExpired:
raise TimeoutError(
"正解を通知した後もプログラムが終了しなかった"
)
if self.proc.returncode != 0:
raise RuntimeError(
f"解答プログラムが異常終了した "
f"(returncode={self.proc.returncode})"
)
def stop(self):
if self.proc.poll() is None:
self.proc.kill()
self.proc.wait()
def print_transcript(self):
print("===== transcript =====")
for side, text in self.transcript:
print(f"{side:8}: {text}")
def print_stderr(self):
if self.stderr_lines:
print("===== stderr =====")
print("".join(self.stderr_lines), end="")
sol_command = prepare(SOL)
for t in range(TEST_COUNT):
case = generate()
io = InteractiveProcess(sol_command)
try:
ok, reason = judge(io, case)
if not ok:
print("WA")
print("===== hidden case =====")
print(repr(case))
print("===== reason =====")
print(reason)
io.print_transcript()
io.print_stderr()
with open("failed.txt", "w") as f:
f.write(repr(case))
io.stop()
break
io.finish()
except TimeoutError as e:
print("TLE!")
print("===== hidden case =====")
print(repr(case))
print("===== reason =====")
print(e)
io.print_transcript()
io.print_stderr()
with open("failed.txt", "w") as f:
f.write(repr(case))
io.stop()
break
except RuntimeError as e:
print("RE / Protocol Error!")
print("===== hidden case =====")
print(repr(case))
print("===== reason =====")
print(e)
io.print_transcript()
io.print_stderr()
with open("failed.txt", "w") as f:
f.write(repr(case))
io.stop()
break
except Exception as e:
print("Judge Error!")
print("===== hidden case =====")
print(repr(case))
print("===== error =====")
print(repr(e))
io.print_transcript()
io.print_stderr()
io.stop()
break
finally:
io.stop()
else:
print("All tests passed!")
・等差数列の和
def rangeSUM(l, r, c):
return (l+r)*c//2
half = pow(2, -1, MOD)
def rangeSUM(l, r, c):
return (l+r)%MOD*c%MOD*half%MOD
・等差数列MODカウント
def rangeModCount(l, r, c, m, k = 0):
if l == r:
return c if l%m == k else 0
if c == 1: return -1
if l > r: l, r = r, l
if (r-l)%(c-1) != 0: return -1
d = (r-l)//(c-1)
GCD = gcd(m, d)
if l%GCD != k%GCD: return 0
ng = (k-l)//GCD
mg = m//GCD
dg = d//GCD
f = inverse(ng, dg, mg)
if c <= f:
return 0
else:
return (c-f-1)//mg+1
・重心分解
size = [-1]*N
maxidx = [-1]*N
@bootstrap
def dfs(n, pre):
history.append(n)
cnt = 1
MAX = -(10**18)
for i, (v, c) in enumerate(G[n]):
if v != pre and not used[v]:
c = yield dfs(v, n)
cnt += c
if MAX < c:
MAX = c
maxidx[n] = i
size[n] = cnt
yield size[n]
@bootstrap
def dfs2(n, L):
if size[G[n][maxidx[n]][0]] > L//2:
yield (yield dfs2(G[n][maxidx[n]][0], L))
yield n
parent = [-1]*N
used = [False]*N
que = deque()
que.append((0, -1))
while que:
n, p = que.popleft()
history = []
dfs(n, -1)
center = dfs2(n, len(history))
while history:
h = history.pop()
size[h] = -1
maxidx[h] = -1
used[center] = True
parent[center] = p
for v, _ in G[center]:
if not used[v]:
que.append((v, center))
・ダブリング
class Doubling:
def __init__(self, nex, max_k=10**18):
self.N = len(nex)
self.LOG = max(1, max_k.bit_length())
self.dp = [[-1]*self.N for _ in range(self.LOG)]
self.dp[0] = nex[:]
for i in range(1, self.LOG):
for j in range(self.N):
self.dp[i][j] = self.dp[i-1][self.dp[i-1][j]]
def jump(self, n, k):
for i in range(self.LOG):
if 1<<i & k:
n = self.dp[i][n]
return n
・LIS
def LIS_length(A, strict=True):
dp = []
bisect = bisect_left if strict else bisect_right
for a in A:
idx = bisect(dp, a)
if idx == len(dp):
dp.append(a)
else:
dp[idx] = a
return len(dp)
def LIS(A, strict=True):
N = len(A)
dp = []
idx = []
pre = [-1]*N
bisect = bisect_left if strict else bisect_right
for i, a in enumerate(A):
j = bisect(dp, a)
if j == len(dp):
dp.append(a)
idx.append(i)
else:
dp[j] = a
idx[j] = i
if j:
pre[i] = idx[j-1]
ans = []
if idx:
now = idx[-1]
while now != -1:
ans.append(now)
now = pre[now]
return ans[::-1]
・トポロジカルソート
def TopologicalSort(G):
N = len(G)
cnt = [0]*N
for n in range(N):
for v in G[n]:
cnt[v] += 1
que = deque()
for n in range(N):
if cnt[n] == 0:
que.append(n)
ans = []
while que:
n = que.popleft()
ans.append(n)
for v in G[n]:
cnt[v] -= 1
if cnt[v] == 0:
que.append(v)
return ans if len(ans) == N else None
・トポロジカルソート（辞書順最小）
def TopologicalSortSmall(G):
N = len(G)
cnt = [0]*N
for n in range(N):
for v in G[n]:
cnt[v] += 1
que = []
for n in range(N):
if cnt[n] == 0:
heappush(que, n)
ans = []
while que:
n = heappop(que)
ans.append(n)
for v in G[n]:
cnt[v] -= 1
if cnt[v] == 0:
heappush(que, v)
return ans if len(ans) == N else None
・転倒数（順列）
# Pは0～N-1の順列
def InversionNumber(P):
N = len(P)
B = BIT([0]*N)
ans = 0
for p in P:
if p+1 < N:
ans += B.query(p+1, N)
B.add(p, 1)
return ans
・転倒数
def InversionNumber(A):
D = compress(A)
L = len(D)
B = BIT([0]*L)
ans = 0
for a in A:
idx = D[a]
if idx+1 < L:
ans += B.query(idx+1, L)
B.add(idx, 1)
return ans
・オイラーツアー（部分木）
class EulerTour:
def __init__(self, G, root=0):
self.G = G
self.N = len(self.G)
self.IN = [-1]*self.N
self.OUT = [-1]*self.N
self.REV = [-1]*self.N
self.dfs(root, -1, 0)
@bootstrap
def dfs(self, n, pre, time):
self.IN[n] = time
self.REV[time] = n
for v in self.G[n]:
if v == pre:
continue
time = yield self.dfs(v, n, time+1)
self.OUT[n] = time
yield time
def index(self, n):
return self.IN[n]
def interval(self, n):
return (self.IN[n], self.OUT[n])
def index_rev(self, n):
return self.REV[n]
・オイラーツアー（パス（辺））
class EulerTour:
def __init__(self, G, root=0):
self.G = G
self.N = len(self.G)
self.IN = [-1]*(self.N-1)
self.OUT = [-1]*(self.N-1)
self.REV = [-1]*((self.N-1)*2)
self.dfs(root, -1, 0)
@bootstrap
def dfs(self, n, pre, time):
for v, eidx in self.G[n]:
if v == pre:
continue
self.IN[eidx] = time
self.REV[time] = eidx
time += 1
time = yield self.dfs(v, n, time)
self.OUT[eidx] = time
self.REV[time] = eidx
time += 1
yield time
def index_in(self, n):
return self.IN[n]
def index_out(self, n):
return self.OUT[n]
def interval(self, n):
return (self.IN[n], self.OUT[n])
def index_rev(self, n):
return self.REV[n]
・オイラーツアー（パス（頂点））
class EulerTour:
def __init__(self, G, root=0):
self.G = G
self.N = len(self.G)
self.IN = [-1]*self.N
self.OUT = [-1]*self.N
self.REV = [-1]*(self.N*2)
self.dfs(root, -1, 0)
@bootstrap
def dfs(self, n, pre, time):
self.IN[n] = time
self.REV[time] = n
time += 1
for v in self.G[n]:
if v == pre:
continue
time = yield self.dfs(v, n, time)
self.OUT[n] = time
self.REV[time] = n
time += 1
yield time
def index_in(self, n):
return self.IN[n]
def index_out(self, n):
return self.OUT[n]
def interval(self, n):
return (self.IN[n], self.OUT[n])
def index_rev(self, n):
return self.REV[n]