2026/10/14

import sys
sys.setrecursionlimit(10 ** 6)　再帰やるならCpython！！！！！！！
from functools import cache
@cache　再起関数のメモ化　return ** の**の計算をメモしてくれる感じ
入力が多い時
from sys import stdin
for _ in range(n):
  x, y, z = map(int, stdin.readline().split())
from collections import defaultdict
dic = defaultdict(int)

s = [[int(a) for a in input().split()] for _ in range(m)]
二次元配列
[list(map(int, input().split())) for _ in range(N)] 
	とすることで行数 N の二次元配列を入力から受け取ることができる
[[0]*M for _ in range(N)] 
	とすることですべての値が 0 のサイズ N×M の二次元配列を作ることができる
[[] for _ in range(N)] 
	とすることでサイズ N×0 の二次元配列(空リストをN 個含むリスト)を作ることができる

print(ans, flush = True) インタラクティブ

yoko = list(map(sum, A)) //行和
tate = list(map(sum, zip(*A))) //列和
x,a = map(list,zip(*sorted(zip(x,a)))) //x,aをxの昇順にソート
#座標圧縮
D = { v: i for i, v in enumerate(sorted(set(A))) }
for a in A:
    print(D[a])

for i, a in sorted(enumerate(A), key=lambda x: x[1]):
aを昇順にしたものを元のindexとともに渡してくれるってやつだと思う

d = math.gcd(a,b,c)　最大公約数　3つ以上も可
chr 数字を文字 unicode
ord 文字を数字
print("".join(map(str,n))) 数値リストを空白無で

外周から何マス離れているか
https://atcoder.jp/contests/abc335/editorial/9067

ｎ頂点ｍ辺の無向グラフ
no = [[] for _ in range(n)]
for _ in range(m):
  a,b = map(int, input().split())
  no[a-1].append(b-1)
  no[b-1].append(a-1)

from sortedcontainers import SortedList
sl = SortedList([3, 1, 4, 1, 5, 9, 2, 6, 5])
add()

連想配列　辞書 abc155c
n = int(input())
s = [input() for _ in range(n)]
dic = {}

for i in range(n):
  if s[i] not in dic:
    dic[s[i]] = 1
  else:
    dic[s[i]] += 1

del my_dict[key] 要素の削除
max = max(dic.values())
ans = []
for k in dic.keys():
  if dic[k] == max:
    ans.append(k)

ans.sort()
for i in ans:
  print(i)
  
SortedSet https://github.com/tatyam-prime/SortedSet/blob/main/SortedSet.py
from sortedcontainers import SortedSet, SortedList, SortedDict

sortedDict = sorted(dictionary, key=lambda x: x[1],reverse = True)

辞書　キー
score_sorted = sorted(score.items(), key=lambda x:x[0])
タプル化()する

辞書のリスト
scores_sorted = sorted(scores, key=lambda x:x['kokugo'])

降順→昇順ソート keyってタプルで複数渡せるんだね
sorted_lst = sorted(lst, key=lambda x: (-x[0], x[1]))

dfs
import sys
sys.setrecursionlimit(10 ** 6)
def dfs(x):
    A = no[x]
    while A != []:
        a = A.pop()
        if used[a] == False:
            A.extend(no[a])
            used[a] = True

for i in range(n):
  if used[i] == False:
    dfs(i)
    k += 1

bfs 
from collections import deque
def bfs(sta):
  d = deque()
  d.append(sta)
  dist = [10**18]*n
  dist[sta] = 0
  while d:
    now = d.popleft()
    for i in edge[now]:
      if dist[i] == 10**18:
        dist[i] = dist[now]+1
        d.append(i)
  return dist


from collections import deque
d = deque()
d.append((0,0))
while(d):
  i,j = d.popleft()
  dis = dist[i][j]
  
  for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
      new_i = i + dy
      new_j = j + dx
      if new_i < 0 or h <= new_i or new_j < 0 or w <= new_j:
        continue
      if grid[new_i][new_j] == '.' and dist[new_i][new_j] > dis+1:
        dist[new_i][new_j] = dis+1
        d.append((new_i, new_j))

startに始点を全部入れる 01-bfsなら0の場合先頭,1の場合末尾に追加
from collections import deque
def bfs(deq, dist):
  d = 0
  while deq:
    i,j = deq.popleft()
    d = dist[i][j]
    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
      new_i = i + dy
      new_j = j + dx
      if new_i < 0 or h <= new_i or new_j < 0 or w <= new_j:
        continue
      if grid[new_i][new_j] == '.' and dist[new_i][new_j] > d:
        dist[new_i][new_j] = d
        deq.appendleft((new_i, new_j))
      elif grid[new_i][new_j] == '#':
        if dist[new_i][new_j] > d+1:
          dist[new_i][new_j] = d+1
          deq.append((new_i, new_j))


dp https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_c
https://atcoder.jp/contests/abc248/editorial/3745　応用版
x = int(input())

dp = [0]*(x+1+105)
dp[0] = 1
for i in range(x+1):
  if dp[i] == 1:
    for j in range(100,106):
      dp[i+j] = 1

if dp[x] == 1:
  print(1)
else:
  print(0)

順列全探索
import itertools
num = list(range(n))
ptn = list(itertools.permutations(num))
組み合わせ
import itertools
c = list(itertools.combinations(l, 2))
同じものを含む順列
from more_itertools import distinct_permutations
for p in distinct_permutations('1122'):
    print(''.join(p))
#1122
#1212
#1221
#2112
#2121
#2211

n個の区別がない球をm個の箱に振り分ける　配分のパターンを出力
from itertools import combinations_with_replacement

def generate_partitions(n, m):
    def dfs(i, rem, cur):
        if i == m:
            if rem == 0:
                res.append(cur[:])
            return
        for x in range(rem + 1):
            cur.append(x)
            dfs(i + 1, rem - x, cur)
            cur.pop()

    res = []
    dfs(0, n, [])
    return res

p =  generate_partitions(n, m)


累積和　https://qiita.com/drken/items/56a6b68edef8fc605821
三次元累積和　https://atcoder.jp/contests/abc366/submissions/68390440
https://atcoder.jp/contests/abc366/submissions/56525738
領域加算ならいもす法　二次元累積和

ソート状態で要素の追加・削除が可能なリスト
https://qiita.com/karutetto332/items/d14c5247d71409ae80e3


deque　先頭末尾どちらも追加できるリスト
from collections import deque
d = deque()
q = int(input())
for i in range(q):
  t,x = map(int, input().split())
  if t == 1:
    d.appendleft(x)
  elif t == 2:
    d.append(x)
  else:
    print(d[x-1])

bit全探索
for bit in range(1 << (N - 1)):  # 1 << (N-1) は 2^(N-1) と同じ
    s = S[0]
    for i in range(N - 1):  # どこにbitが立ってるかを確認していく
        if bit & (1 << i):

for bit in product((0, 1), repeat=N - 1):

メモ化再帰→DP変換　最大値試して間に合わないなら書き換えよう！

import sys
sys.setrecursionlimit(10 ** 6)
from functools import cache
n = int(input())
a = list(map(int, input().split()))
'''@cache
def dp(l,r):
  if l+1 == r:
    return a[l]
  return max(a[l]-dp(l+1,r),a[r-1]-dp(l,r-1))'''

dp = [[0] * (n + 1) for _ in range(n + 1)]

for length in range(1, n + 1):  # 区間の長さ
    for l in range(n - length + 1):
        r = l + length
        if l+1 == r:
          dp[l][r] = a[l]
        else:
          dp[l][r] = max(a[l]-dp[l+1][r],a[r-1]-dp[l][r-1])

ans = dp[0][n]
print(ans)

累乗高速計算　繰り返し二乗法ってのもあるらしい　pow(a,b,mod)でいいらしい
  def pow_k(x,n):
    if n == 0:
      return 1
    
    k = 1
    while n > 1:
      if n % 2 != 0:
        k *= x
      x *= x % inf 
      n //= 2
    return k * x % inf

素数判定等々　ルートnまで全部割ればいいらしい？
for p in range(15):
  if prime[p]:
    for i in range(p*p,201,p):
      prime[i]=False

def get_prime(n):
    sieve = [True] * (n + 1) 
    i = 2
    while i * i <= n: 
        if sieve[i]:
            for j in range(i * i, n + 1, i):
                sieve[j] = False
        i += 1
    return [i for i in range(2, n + 1) if sieve[i]]  

print(get_prime(100))
素数のリストを返す

素因数の数
c = [0]*(n+1)
ans = 0
for i in range(2,n+1):
  if c[i] == 0:
    for j in range(i,n+1,i):
      c[j] += 1

約数列挙　
div = [0]*(N+1)
for n in range(1, N+1):
  for m in range(n, N+1, n):
    div[m] += 1

逆元 modをつかえば求められるらしい　使うときがきたら随時調べよう

inv = pow(a, mod - 2, mod)

#階乗　二項係数
MOD = 998244353

N = 5 * 10**6
fact = [1] * (N + 1)       # 階乗
inv_fact = [1] * (N + 1)   # 階乗の逆元

# 階乗の前計算
for i in range(1, N + 1):
    fact[i] = fact[i - 1] * i % MOD

# 階乗逆元の前計算
inv_fact[N] = pow(fact[N], MOD - 2, MOD)  # フェルマーの小定理
for i in range(N - 1, -1, -1):
    inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD
def comb(n, k):
    if k < 0 or k > n:
        return 0
    return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD

区別できない球n個/できる箱k個
n+k-1 C n = n+k-1 C k-1


from bisect import bisect_right, bisect_left, insort_left, insort_right
import bisect

二分探索　最小値の最大化　答えを決め打ちしちゃうパターン　単調性がある場合も使えるよ
#l < rで最大、l > rなら最小が求まる 条件を満たしていたらTrue
l = 0 #解が存在
r = L #解が存在しない
while abs(l-r) > 1:
  m = (l+r)//2
  if check(m):
    l = m
  else:
    r = m
print(l)

三分探索
l,r=0,10**18
p = pow(10,-7)　#整数なら2にしてl~rを調べる
while l+p<r:
    c1=l+(r-l)/3
    c2=r-(r-l)/3
    if f(c1)<f(c2):
      r=c2
    else:
      l=c1

二部グラフ
https://atcoder.jp/contests/typical90/tasks/typical90_z

union-find ac-libraryを使えるようになろう

from atcoder.dsu import DSU
'''uf = DSU(n) : 初期化(nは頂点数)
uf.merge(u, v) : 「頂点uの連結成分」と「頂点vの連結成分」を結合する。この連結成分の代表元を返す。
uf.same(u, v) : 2頂点uvが同じ連結成分ならTrueを、そうでない場合はFalseを返す。
uf.leader(u) : 頂点uの連結成分の代表元を返す。
uf.size(u) : 頂点uの連結成分の頂点数を返す。
uf.groups() : 各連結成分のリストを返す (各連結成分がそれぞれリストになっていて、全体として2次元リスト)。
'''
n,m = map(int, input().split())
uf = DSU(n)
for _ in range(m):
  u, v = map(int, input().split())
  u -= 1
  v -= 1
  uf.merge(u, v)

ans = uf.groups()
print(len(ans))

min_pos = list(range(n))
def merge_with_min(u, v) :
    lu = uf.leader(u)
    lv = uf.leader(v)
    if lu == lv:
        return
    uf.merge(u, v)
    new_leader = uf.leader(u)
    min_pos[new_leader] = min(min_pos[lu], min_pos[lv])
min_pos[]に代表元を投げたら左端が返って来るよ

バックトラック
探索済→再起呼び出し→探索済解除（つまり1手戻る）
def dfs(r,c,xy,n):
  global ans
  for k in range(4):
    nx = r + dx[k]
    ny = c + dy[k]
    if 0 <= nx < h and 0 <= ny < w and grid[nx][ny] == '.':
      if nx == i and ny == j:
        ans = max(ans,n+1)
      elif tf[nx][ny] == False:
        tf[nx][ny] = True
        dfs(nx,ny,xy,n+1)
        tf[nx][ny] = False

https://atcoder.jp/contests/abc310/submissions/66038624
チーム分けバックトラック

3^n bitdp
部分集合の部分集合
res = (1<<n)-1 ^ j
k = res
while k > 0:
  k = (k-1)&res



メモ化再帰
def dfs(v):
    if dp[v] != -1:
        return dp[v]
    max_len = 0
    for u in G[v]:
        max_len = max(max_len, dfs(u) + 1)
    dp[v] = max_len
    return dp[v]

ans = 0
for v in range(N):
    ans = max(ans, dfs(v))



ダイクストラ　https://atcoder.jp/contests/abc362/submissions/55346606
from heapq import heappush, heappop
def dijkstra(G, s):
    INF = 10**18
    dist = [INF] * len(G)
    dist[s] = 0
    pq = [(0, s)]
    while pq:
        d, v = heappop(pq)
        if d > dist[v]:
            continue
        for u, weight in G[v]:
            nd = d + weight
            if dist[u] > nd:
                dist[u] = nd
                heappush(pq, (nd, u))
    return dist

ワーシャルフロイド
INF = float('inf')  # 無限大を表す値

def warshall_floyd(graph):
    """
    ワーシャル・フロイド法で全点対間最短経路を計算する

    Args:
        graph: 隣接行列形式のグラフ (2次元リスト)
               graph[i][j] は頂点iからjへの辺のコスト。
               辺が存在しない場合は INF。

    Returns:
        全点対間最短経路の距離行列 (2次元リスト)
    """
    n = len(graph)
    dist = [row[:] for row in graph]  # graph のコピーを作成

    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist


int.bit_count()
ある整数を2進数表記したときに、そこに含まれている1の数を返すメソッドです。
print(x.bit_count())  # 3 (13の2進数表記は1101)

桁dp
https://atcoder.jp/contests/abc406/submissions/66007596 2進数
https://qiita.com/takayg1/items/a5c1cadbc8b89daa0fd5 ０でない数をk個含むN以下の数の総数

分数の誤差回避
https://atcoder.jp/contests/adt_all_20250618_1/submissions/66862060
XOR基底 https://atcoder.jp/contests/typical90/submissions/67172995
#xor基底
def xor_basis(A):
    basis = [0] * 301  # 最大60ビットくらい（10^18以下）
    for x in A:
        for i in reversed(range(301)):  # 高位ビットから
            if not (x >> i) & 1:
                continue
            if basis[i] == 0:
                basis[i] = x
                break
            x ^= basis[i]
    return [b for b in basis if b != 0]  # 基底集合
    
def can_make(x, basis):
    for b in reversed(basis):  # 高位ビットから
        if (x ^ b) < x:
            x ^= b
    return x == 0


LCA(最小共通祖先) https://tjkendev.github.io/procon-library/python/graph/lca-st.html
セグメント木　https://qiita.com/hyouchun/items/3eee499a7ef31ca55b46

from atcoder.segtree import SegTree
'''
st = SegTree(op, e, v) : セグメントツリーを構築する。opは区間の演算につかう関数、eはその単位元。
 vにはlist型かint型を入れる。list型の場合はそのリストをそのまま入り、
 int型の場合はすべての要素が単位元eで長さvのリストになる。
st.set(p, x) : リストAについて、Apにxを代入する。
st.get(p) : リストAのp番目の要素Apを返す。
st.prod(l, r) : 半開区間[l:r)における演算の結果を返す。
st.all_prod() : リスト全体における演算の結果を返す。
st.max_right(p, func) : セグメントツリー上で二分探索をする。
 p <= iを満たすiの中で、関数funcが初めてFalseになるiを返す。(最小)
st.min_left(p, func) : セグメントツリー上で二分探索をする。
 i<pを満たすiの中で、関数funcが初めてFalseになるiを返す。(最大)

a[x]がnow以下の添字、max_right
e = 10**18
def op(x,y):
  return min(x,y)
def func(x):
  return x > now
st = SegTree(op, e, a)

自前セグ木 https://atcoder.jp/contests/awc0082/submissions/76955238

非再帰dfs グラフを行きがけ順に並べて、indexを保持したい！
def dfs_iterative(root, edge):
    n = len(edge)
    ind = [[] for _ in range(n)]
    lis = [0]*n
    num = 0
    stack = [(root, -1, 0)]  # (current_node, parent, state)
    while stack:
        now, before, state = stack.pop()
        if state == 0:
            # 入り時処理
            ind[now].append(num)
            lis[now] = num
            num += 1
            stack.append((now, before, 1))  # 帰り時用に再プッシュ
            for nxt in reversed(edge[now]):
                if nxt != before:
                    stack.append((nxt, now, 0))
        else:
            # 帰り時処理
            ind[now].append(num)
    return lis, ind



「各要素が最小値となる区間の幅」を求める処理は、単調スタック (Monotonic Stack) を使うことで に高速化できます。
l = [-1] * n
r = [n] * n
stack = []
for i in range(n):
  while stack and a[stack[-1]] >= a[i]:
    stack.pop()
  if stack:
    L[i] = stack[-1]
  stack.append(i)
  
stack = []
for i in range(n - 1, -1, -1):
  while stack and a[stack[-1]] > a[i]:
    stack.pop()
  if stack:
    R[i] = stack[-1]
  stack.append(i)

# 寄与分の計算と辞書への格納
for i in range(n):
  count = (i - L[i]) * (R[i] - i)
  key = a[i] ^ R_val # 元のコードのR
  if key not in dic:
    dic[key] = [0, pow(a[i], -1, mod)]
  dic[key][0] += count

x mod a が1、他が0の時、i以下の総和
(i-x)//a + 1 
3 mod 4　で9なら2

回文判定 https://snuke.hatenablog.com/entry/2014/12/03/214243
def manacher(ss):
  #文字iを中心とする最長の回文の半径
  S = ['$']
  for i in ss:
    S.append(i)
    S.append('$')

  S = "".join(S)
  i = 0
  j = 0
  n = len(S)
  R = [0]*n

  while i < n:
    while (i-j >= 0) and (i+j < n) and (S[i-j] == S[i+j]):
      j += 1
    R[i] = j
    k = 1
    while (i-k >= 0) and (k+R[i-k] < j):
      R[i+k] = R[i-k]
      k += 1
    i += k
    j = max(j-k,0)
  
  return R,S

def max_kaibun(s):
    R,S = manacher(s)
    max_len = max(R)
    center = R.index(max_len)
    start = center - max_len + 1
    end = center + max_len
    # 回文部分の加工済み文字列区間を取り出し、
    # 区切り文字'$'を除いて元文字列の回文を復元
    pal = ''.join([c for c in S[start:end] if c != '$'])
    return pal


Z-algorithm SとS[i:]の最長共通接頭辞の長さをO(N)で
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
幾何
https://atcoder.jp/contests/math-and-algorithm/submissions/65055869　点と線分の最短距離
https://atcoder.jp/contests/agc036/submissions/66047649　三角形の面積
https://atcoder.jp/contests/math-and-algorithm/submissions/65058616　線分の交差判定　chatGPT
https://atcoder.jp/contests/abc442/submissions/72725503　偏角ソート　象限ごとにやればいい
45度回転 x-y,x+y(マンハッタンの場合)

平方根
def f(x):
  y = int(pow(x,0.5))
  while y*y > x:
    y -= 1
  while (y+1)*(y+1) <= x:
    y += 1
  return y

import math
math.isqrt(x)
で良さそう？

線の傾き
import math
def slope(x1, y1, x2, y2):
  dy = y2 - y1
  dx = x2 - x1
  if dx == 0:
    return (1, 0)
  if dy == 0:
    return (0, 1)
    
  g = math.gcd(dy, dx)
  dy //= g
  dx //= g

  if dx < 0:
    dx = -dx
    dy = -dy
    
  return (dy, dx)

a xor b = a + b - 2(a and b)

alien DP 飴DP　？
https://atcoder.jp/contests/awc0156/submissions/79264217

Mo's algo (codon)
https://atcoder.jp/contests/abc477/submissions/79570050

2026/10/14
Atcoder　ライブラリまとめ②　水↑くらいで使いそうなものを主に

中国剰余定理
def extgcd(a, b):
    if b:
        d, y, x = extgcd(b, a % b)
        y -= (a // b) * x
        return d, x, y
    return a, 1, 0

# V = [(X_i, Y_i), ...]: X_i (mod Y_i)
def remainder(V):
    x = 0; d = 1
    for X, Y in V:
        g, a, b = extgcd(d, Y)
        x, d = (Y*b*x + d*a*X) // g, d*(Y // g)
        x %= d
    return x, d



永続スタック　https://atcoder.jp/contests/abc273/submissions/67457517
# --- 永続スタック定義 ---
class Node:
    def __init__(self, value, prev):
        self.value = value
        self.prev = prev

class PersistentStack:
    def __init__(self, top=None):
        self.top = top

    def push(self, value):
        return PersistentStack(Node(value, self.top))

    def pop(self):
        if self.top is None:
            return self
        return PersistentStack(self.top.prev)

    def peek(self): #末尾の値を返す
        return -1 if self.top is None else self.top.value


Q = int(input())
#dicにAを入れてもポインタが入るからO(1)のはず？
A = PersistentStack()



Modint mint
class mint:
    MOD = 998244353

    def __init__(self, n):
        self._n = int(n) % mint.MOD

    def __str__(self):
        return str(int(self._n))

    def __repr__(self):
        return f'{self._n} mod {mint.MOD}'
        
    def __format__(self, format_spec):
        return format(int(self), format_spec)

    def __index__(self):
        return self._n
    
    def __eq__(self, value):
        return isinstance(value, (int, mint)) and self._n == int(value)
    
    def __hash__(self):
        return hash(self._n)
    
    def __add__(self, other):
        return mint(self._n + int(other))

    def __sub__(self, other):
        return -(-self + other)
    
    def __mul__(self, other):
        return mint(self._n * int(other))

    def __truediv__(self, other):
        return self * mint(other) ** (-1)

    def __pow__(self, other: int):
        return mint(pow(self._n, other, mint.MOD))

    def __radd__(self, other):
        return self + other

    def __rsub__(self, other):
        return -self + other

    def __rmul__(self, other):
        return self * other

    def __rtruediv__(self, other):
        return mint(other) * self ** (-1)

    def __iadd__(self, other):
        return self + other

    def __isub__(self, other):
        return self - other
    
    def __imul__(self, other):
        return self * other
    
    def __ipow__(self, other: int):
        return self ** other
    
    def __itruediv__(self, other):
        return self / other

    def __neg__(self):
        return mint(-self._n)
    
    def __pog__(self):
        return self

自作関数
class MyClass:
    def __init__(self, val):
        self.val = val  # インスタンス変数

    def show(self):
        print(f"MyClass has value: {self.val}")

    def update(self, new_val):
        self.val = new_val

Trie木
class Trie:
    class Node:
        def __init__(self):
            self.child = [-1] * 26  # 子ノードのインデックス配列（-1は未接続）
            self.is_end = False     # ここで単語が終わるかどうかのフラグ

    def __init__(self):
        self.nodes = [self.Node()]  # ルートノード（インデックス0）

    def add(self, s):
        k = 0  # 現在のノードインデックス（最初はルート）
        for c in s:
            c_idx = ord(c) - ord('a')
            node = self.nodes[k]
            if node.child[c_idx] == -1:
                node.child[c_idx] = len(self.nodes)
                self.nodes.append(self.Node())
            k = node.child[c_idx]
        self.nodes[k].is_end = True  # 文字列の終端をマーク


trie = Trie()

binary_trie
class SimpleBinaryTrie:
    def __init__(self, max_bits=30):
        # max_bits: 扱う数値の最大ビット数 (30なら 0 <= x < 2^30)
        self.max_bits = max_bits
        # 各ノードは [0の枝のノード, 1の枝のノード, 部分木に含まれる要素数]
        self.root = [None, None, 0]

    def insert(self, val):
        """値 val を追加する"""
        node = self.root
        node[2] += 1
        for i in range(self.max_bits - 1, -1, -1):
            bit = (val >> i) & 1
            if node[bit] is None:
                node[bit] = [None, None, 0]
            node = node[bit]
            node[2] += 1

    def erase(self, val):
        """値 val を1つ削除する (※Trie内に存在することが前提)"""
        if self.root[2] == 0:
            return
        node = self.root
        node[2] -= 1
        for i in range(self.max_bits - 1, -1, -1):
            bit = (val >> i) & 1
            next_node = node[bit]
            next_node[2] -= 1
            if next_node[2] == 0:
                # 要素がなくなったらメモリ節約とバグ防止のために枝ごと切り落とす
                node[bit] = None
                return
            node = next_node

    def get_min_xor(self, x):
        """Trie内の要素 y と x の XOR (y ^ x) が【最小】となる値を返す"""
        if self.root[2] == 0:
            return -1  # 空の場合は -1 を返す
        
        node = self.root
        ans = 0
        for i in range(self.max_bits - 1, -1, -1):
            bit = (x >> i) & 1
            # 最小化したいので、x のビットと「同じ方向（XORが0になる方向）」を優先
            if node[bit] is not None:
                node = node[bit]
            else:
                ans |= (1 << i)
                node = node[bit ^ 1]
        return ans

    def get_max_xor(self, x):
        """Trie内の要素 y と x の XOR (y ^ x) が【最大】となる値を返す"""
        if self.root[2] == 0:
            return -1  # 空の場合は -1 を返す
            
        node = self.root
        ans = 0
        for i in range(self.max_bits - 1, -1, -1):
            bit = (x >> i) & 1
            # 最大化したいので、x のビットと「逆の方向（XORが1になる方向）」を優先
            rev_bit = bit ^ 1
            if node[rev_bit] is not None:
                ans |= (1 << i)
                node = node[rev_bit]
            else:
                node = node[bit]
        return ans


# 1. 初期化 (扱う数値の最大値に合わせてビット数を指定します。10^9程度なら30で十分です)
trie = SimpleBinaryTrie(max_bits=30)

# 2. 値の追加
A = [6, 12, 3]
for a in A:
    trie.insert(a)

# 3. ある値 x との XOR の最小値・最大値を取得 (Trieの中身は消えません)
x = 5
print(f"5とのXORの最小値: {trie.get_min_xor(5)}")  # 出力: 3 (∵ 6 ^ 5 = 3)
print(f"5とのXORの最大値: {trie.get_max_xor(5)}")  # 出力: 9 (∵ 12 ^ 5 = 9)

# 4. 値の削除
trie.erase(6) # 6 をTrieから取り除く

# 5. 削除後の再確認
print(f"6削除後の5とのXORの最小値: {trie.get_min_xor(5)}") # 出力: 6 (∵ 3 ^ 5 = 6)

indexも返すセグ木
def op(a, b):
    return a if a[0] >= b[0] else b

e = (0, -1)
seg = SegTree(op, e, [(0, -1)] * h)



フェニック木
https://qiita.com/AkariLuminous/items/f2f7930e7f67963f0493
class Fenwick_Tree:
    def __init__(self, n):
        self._n = n
        self.data = [0] * n
    
    def add(self, p, x):
        assert 0 <= p < self._n
        p += 1
        while p <= self._n:
            self.data[p - 1] += x
            p += p & -p
    
    def sum(self, l, r):
        assert 0 <= l <= r <= self._n
        return self._sum(r) - self._sum(l)
    
    def _sum(self, r):
        s = 0
        while r > 0:
            s += self.data[r - 1]
            r -= r & -r
        return s



遅延セグ木 abc332f 
from atcoder.lazysegtree import LazySegTree

ls = LazySegTree(op, e, mapping, composition, _id, lst) : 遅延セグメントツリーを構築する。引数は以下の通り。
op : 区間取得の演算
e : opの単位元
mapping : dataにlazyを作用させたときの関数
composition : lazyに別のlazyを作用させたときの関数
_id : mappingの恒等写像
lst : 初期リスト

ls.apply(l, r , f) Aiにfを作用
ls.set(p, x) Apにxを代入
ls.get(p) : Apを返す
ls.prod(l, r) : 半開区間[l:r)における演算の結果を返す。
ls.all_prod() : リスト全体における演算の結果を返す。
ls.max_right(p, func) : セグメントツリー上で二分探索をする。 
 p<=iを満たすiの中で、関数funcが初めてFalseになる最小のiを返す。
ls.min_left(p, func) : セグメントツリー上で二分探索をする。 
i<pを満たすiの中で、関数funcが初めてFalseになる最大のiを返す。

def op(data1, data2):
    return max(data1, data2)

# opの単位元 op(data1, e) = data1
e = -float("Inf")

# lazyをdataに作用させる
def mapping(lazy_upper, data_lower):
    return (data_lower * lazy_upper[0] + lazy_upper[1])%mod

# lazyをlazyに作用させる
def composition(lazy_upper, lazy_lower):
    return (lazy_upper[0] * lazy_lower[0])% mod, (lazy_upper[0] * lazy_lower[1] + lazy_upper[1]) % mod

# mapping(_id, data_lower) = data_lower
_id = (1,0)

ls = LazySegTree(op, e, mapping, composition, _id, a)





abc417f 区間和・区間更新
from atcoder.lazysegtree import LazySegTree
mod = 998244353
ID = 10**18
def op(x, y):
    return ((x[0] + y[0]) % mod, x[1] + y[1])

e = (0, 0)

def mapping(f, x):
    if f == ID:
        return x
    return (f * x[1] % mod, x[1])

def composition(f, g):
    if f == ID:
        return g
    return f

_id = ID

n, m = map(int, input().split())
a = list(map(int, input().split()))
init = [(val, 1) for val in a]  # 各皿は1つ分のサイズ
seg = LazySegTree(op, e, mapping, composition, _id, init)

for _ in range(m):
    l, r = map(int, input().split())
    l -= 1
    total, length = seg.prod(l, r)
    avg = total * pow(length, -1, mod) % mod
    seg.apply(l, r, avg)

print(*[seg.get(i)[0] for i in range(n)])


フェルマーの小定理（累乗？）
(p-1) = 998244352
φ(p−1)=402653184

#LISに含まれる可能性のあるすべての要素
def find_all_lis_elements(arr):
    n = len(arr)
    if n == 0:
        return []

    # ステップ1: 各要素で終わるLISの長さを計算する
    dp = [1] * n
    for i in range(n):
        for j in range(i):
            if arr[i] > arr[j]:
                dp[i] = max(dp[i], dp[j] + 1)

    # ステップ2: LISの最大長を求める
    max_len = 0
    if dp:
        max_len = max(dp)

    if max_len == 0:
        return []
    
    # ステップ3: LISの要素を逆順に特定する
    lis_elements = set()
    
    # LISの最大長を持つ要素から探索を開始
    
    # 現在のLISの長さと、現在の探索インデックスのリスト
    current_lis_len = max_len
    current_indices = [i for i, length in enumerate(dp) if length == current_lis_len]
    
    while current_lis_len > 0:
        next_indices = []
        
        # 現在の長さのLISの末尾となる要素をすべてlis_elementsに追加
        for idx in current_indices:
            lis_elements.add(arr[idx])

            # 次のステップ（長さが1つ短いLIS）に進むための親要素を探す
            for j in range(idx):
                # arr[j]がarr[idx]より小さく、かつdp[j]が現在の長さ-1と等しい場合
                if arr[j] < arr[idx] and dp[j] == current_lis_len - 1:
                    next_indices.append(j)

        current_lis_len -= 1
        current_indices = list(set(next_indices)) # 重複を削除

    return sorted(list(lis_elements))

# 使用例
arr = [3, 1, 4, 5, 9]
result = find_all_lis_elements(arr)
print(f"元の配列: {arr}")
print(f"すべてのLISを構成するユニークな数字: {result}")


全方位木DP https://atcoder.jp/contests/abc428/submissions/70282562
class Rerooting:
    def __init__(self, n, merge, add_root, e):
        self.n = n
        self.g = [[] for _ in range(n)]
        self.merge = merge
        self.add_root = add_root
        self.e = e
        self.dp_down = [e] * n
        self.dp_all = [e] * n

    def add_edge(self, u, v, w=1):
        self.g[u].append((v, w))
        self.g[v].append((u, w))

    def solve(self, root=0):
        n = self.n
        g = self.g
        merge = self.merge
        add_root = self.add_root
        e = self.e

        # ---- 非再帰 DFS1 ----
        parent = [-1] * n
        order = []
        stack = [root]
        while stack:
            v = stack.pop()
            order.append(v)
            for c, w in g[v]:
                if c == parent[v]:
                    continue
                parent[c] = v
                stack.append(c)

        for v in reversed(order):
            res = e
            for c, w in g[v]:
                if c == parent[v]:
                    continue
                res = merge(res, add_root(self.dp_down[c], c, w))
            self.dp_down[v] = res

        # ---- 非再帰 DFS2 ----
        stack = [(root, e)]
        while stack:
            v, from_parent = stack.pop()
            children = [(c, w) for c, w in g[v] if c != parent[v]]
            m = len(children)
            dpL = [e] * (m + 1)
            dpR = [e] * (m + 1)

            for i in range(m):
                c, w = children[i]
                dpL[i + 1] = merge(dpL[i], add_root(self.dp_down[c], c, w))
            for i in range(m - 1, -1, -1):
                c, w = children[i]
                dpR[i] = merge(add_root(self.dp_down[c], c, w), dpR[i + 1])

            self.dp_all[v] = merge(from_parent, self.dp_down[v])

            for i, (c, w) in enumerate(children):
                without_c = merge(dpL[i], dpR[i + 1])
                new_from_parent = add_root(merge(from_parent, without_c), v, w)
                stack.append((c, new_from_parent))

        return self.dp_all


# =====================
# 問題に合わせた設定
# =====================
def merge(a, b):
    if a[0] > b[0]:
        return a
    if a[0] < b[0]:
        return b
    return (a[0], max(a[1], b[1]))


def add_root(x, v, w):
    if x[1] != -1:
        return (x[0] + w, x[1])
    return (x[0] + w, v)

n = int(input())
e = (0, -1)

rr = Rerooting(n, merge, add_root, e)

for _ in range(n - 1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  rr.add_edge(a, b)

dp_all = rr.solve(0)

for v in range(n):
  print(dp_all[v][1] + 1)

💡 具体的な例をいくつか
① 各頂点からの距離総和（全方位）
https://atcoder.jp/contests/abc348/submissions/75130077
cは頂点重み
# 各頂点に対して「他の全頂点までの距離総和」
merge = lambda a, b: (a[0]+b[0],a[1]+b[1])
add_root = lambda x, v, w: (x[0]+(x[1]+c[v])*w,x[1]+c[v])
e = (0,0)

② 各頂点から最も遠い距離

👉 今の例（distance-only版）

③ 各頂点を根としたときの「部分木サイズ」
merge = lambda a, b: a + b
add_root = lambda x, v, w: x + 1  # 自分自身を足す
e = 0

④ 各頂点からの「最大部分木深さ」

👉 高さ計算。

merge = lambda a, b: max(a, b)
add_root = lambda x, v, w: x + w
e = 0

⑤ 木の直径の長さ（全方位）

2本の最長距離を保持すればOK：

merge = lambda a, b: sorted([a, b], reverse=True)[:2]  # 上位2本
add_root = lambda x, v, w: [x[0] + w, 0]  # 長さを1足す
e = [0, 0]


→ 各頂点で sum(top2) が「直径通る最大距離」。

⑥ 木の最大値・最小値を併せた情報伝搬

各頂点に値 A[v] があるとき：

merge = lambda a, b: (max(a[0], b[0]), min(a[1], b[1]))
add_root = lambda x, v, w: x
e = (-10**18, 10**18)


→ 各頂点を根としたときの「部分木中の最大・最小値」が取れる。


重み付きUnionFind、重み付きUF
undo可能（ただしlogn) https://atcoder.jp/contests/awc0100/submissions/76976530

ロリハ　ローリングハッシュ
基数 37 137 998244353
mod 998244853 10**9+7 2**61-1

行列積
def op(x,y):
  l = len(x)
  m = len(x[0])
  r = len(y[0])
  mat = [[0]*r for _ in range(l)]
  for i in range(l):
    for j in range(r):
      for k in range(m):
        mat[i][j] += x[i][k]*y[k][j]
        mat[i][j] %= mod
  return mat

import random
import string

# ======== 本解をここに実装 ========
def solve(*args):
    # ここに本解（高速な実装など）を書く
    return None


# ======== ここに愚直解を書く ========
def brute(*args):
    # ここに愚直解（構築・全探索など）を書く
    return None


# ======== 入力生成関数 ========
def generate_input():
    # ランダム入力を作る
    # 必要に応じて下記の変数を調整
    N = random.randint(1, 10)  # 整数1つ
    M = random.randint(0, 100)  # 整数2つ目（あれば）

    # ランダムな文字列
    S = ''.join(random.choices(string.ascii_lowercase, k=N))

    # ランダムな整数リスト
    A = [random.randint(0, 100) for _ in range(N)]

    # ランダムな2次元配列（例えば M×N）
    grid = [[random.randint(0, 1) for _ in range(N)] for _ in range(M)]

    # 必要なものをreturnする（複数引数でもOK）
    return N, M, S, A, grid


# ======== テスト実行部 ========
def test():
    for _ in range(1000):
        inputs = generate_input()
        try:
            ans1 = solve(*inputs)
            ans2 = brute(*inputs)
        except Exception as e:
            print("⚠️ Exception during execution")
            print("Inputs:", inputs)
            print("Error:", e)
            return
        if ans1 != ans2:
            print("❌ WA")
            print("Inputs:", inputs)
            print("solve:", ans1)
            print("brute:", ans2)
            return
    print("✅ All tests passed!")

test()