README.md

math

library for math

geometry

geometry.hpp
幾何に関するライブラリ

• point2d: 2次元座標, ベクトル
• point3d: 3次元座標, ベクトル
• convex hull (by graham, upper, lowerのwhile条件式の等号を外すと内角180度に対応できる)
  verify: AOJ(Convex Hull)
• plane equation
  verify: yukicoder(点と平面との距離)
• projection
  verify: AOJ(Projection)
• reflection
  verify: AOJ(Reflection)
• parallel, orthogonal
  verify: AOJ(Parallel/Orthogonal)
• intersection
  verify: AOJ(Intersection)
• closest pair
  verify: AOJ(Closest Pair)
  verify: AtCoder(Big Bang)
• circle intersection
  verify: AOJ(Intersection)
• square test
  veriry: yukicoder(正方形を描くだけの簡単なお仕事です。)

power

power.hpp
繰り返し二乗法で累乗を求める.

• power by doubling
  verify: AOJ(Power)

prime

prime.hpp
素数に関するモジュール

• check if the number is a prime number
• list all prime number lower than or equals to a number
• list all prime number in [a, b) (b - a should be small enough)
• list devisors
• prime factorization
  verify: AOJ(Prime Factorize)
• millar rabin algorithm
  verify: yukicoder(tatyamと素数大富豪)
• euler's phi function
  verify: AOJ(Euler's Phi Function)

algebra

algebra.hpp
主に余りに関するモジュール

• greatest common devider
  verify: AOJ(Least Common Multiple)
• extgcd
  verify: Extended Euclid Algorithm
• modinv
• modlog (baby step giant step)
• Garner Algorithm
• arbitrary mod garner algorithm
  verify: yukicoder(中華風 (Hard))
• chinese reminder theorem
  verify: yukicoder(中華風 (Easy))
• factorial, combination, permutation, h
  verify: yukicoder(組み合わせの数)

convex hull trick

convex_hull_trick.hpp
複数の直線の中で最小の値を求める

• monotonious update of lines(monotonious decrease of slope, minimum query)
• Li Chao Tree
  verify: AtCoder(スペースエクスプローラー高橋君)
  verify: Codeforces(Lena and Queries)

matrix

matrix.hpp
ガウスの掃き出し法など

• gauss jordan
• gauss jordan (mod p)
• gauss jordan (bit)
• matrix power

interpolation

interpolation.hpp
多項式補間

• lagrange interpolation for double
• lagrange interpolation for T (ex. modint)
• lagrange interpolation for [0..N]
  verify: AtCoder(見たことのない多項式)

ModInt

modint.hpp
剰余体での演算

• modint

Convolution

convolution.hpp
FFT, Convolution

• convolution
  verify: AtCoder(高速フーリエ変換)
• fft (dft, idft)
  verify: AtCoder(高速フーリエ変換)
• NTT, arbitrary mod convolution
  verify: AtCoder(高速フーリエ変換)

Rational

rational.hpp
有理数ライブラリ

• stern brocot tree
  verify: yukicoder(貯金箱の消失)

set by bit

set_by_bit.hpp
bitを用いた集合演算

• next_combination

combination

combination.hpp
二項係数(modが素数でない場合)

• fixed base combination verify: AtCoder(Don't worry. Be Together)