# RAINBOU Library

## リポジトリ
https://github.com/rainbou-kpr/library

公開しますか？
yes

何人いますか？
7人いる

- 基本的に自由にIssue/PRを立てて、ディスカッションはDiscord #ライブラリ でやる

## 作るもの/ディレクトリ構成
レベル順の星をつけたい

- グラフ
- [x] Dijkstra
- [ ] bellman-ford
- [x] topological-sort
- [ ] maxflow
- [ ] mincostflow
- [ ] 強連結成分分解
- [x] LCA(ダブリング)
- [ ] HL分解
- [x] Euler Tour
- [ ] 重心分解
- [ ] Link-Cut木
- [x] 直径、中心
- [ ] manhattan MST
- [ ] 橋
- [ ] 木の同型判定
- 代数
- [x] 行列
- [ ] XOR基底
- [x] modint
- [x] NTT
- [ ] 64bit整数畳み込み
- [x] 任意mod畳み込み
- [ ] 高速アダマール変換
- [ ] 高速ゼータ変換
- [ ] 高速メビウス変換
- [ ] 添字OR畳み込み
- [ ] 添字AND畳み込み
- [ ] 添字GCD畳み込み
- [ ] FPS
- 数論
- [ ] floor-sum
- [ ] CRT
- [ ] BabyStep-GiantStep
- [ ] modpow
- [ ] modinv
- [ ] 素数列挙
- [ ] 素因数分解
- [ ] 約数列挙
- [ ] エラトステネスの篩
- [ ] オイラーのφ関数
- [ ] 拡張ユークリッドの互除法
- [ ] Kth term of Linearly Recurrent Sequence
- [x] 平方根(floor(sqrt(N)), 二分探索)
- [ ] n乗根(mod, integer)
- 数え上げ
- [x] 階乗・階乗逆元を保持してP,C,Hが高速に出るやつ
- [ ] 写像12相
- [ ] モンモール数
- [ ] カタラン数
- 幾何
- [x] 線分の交差点
- [x] 多角形の面積
- [x] 多角形が点を含むか
- [x] 最近点対
- [x] 凸包
- [ ] Convex Hull Trick
- データ構造
- [x] セグ木
- [x] 遅延セグ木
- [x] Beats
- [ ] BIT
- [ ] 動的セグ木
- [x] 二次元セグ木
- [ ] 双対セグ木
- [ ] Sparse Table
- [ ] Wavelet Matrix
- [ ] SWAG
- [ ] Slope-trick
- [ ] Treap
- [ ] AVL木
- [ ] RBST
- [ ] 遅延伝搬反転可能乱択平衡二分木
- [ ] 赤黒木
- [ ] 永続配列
- [x] Union-Find
- [ ] 永続Union-Find
- [ ] 永続セグ木
- [x] 重み付きUnion-Find
- 文字列
- [x] ローリングハッシュ
- [ ] KMP
- [ ] Trie木
- [ ] Aho-corasick
- [x] Z-Algorithm
- [ ] suffix-array
- その他
- [ ] Mo-algorithm
- [ ] 三分探索(黄金探索？)
- [ ] 並列二分探索
- [ ] 牛ゲー
- [ ] 2-SAT
- [ ] 転倒数
- [ ] 全方位木DP
- [x] 転置
- [x] 回転
- [x] 上下、左右反転
- [ ] ランレングス圧縮
- [x] (C++のみ)入出力(空白区切り、vectorなど)

## include/import展開
### C++
[oj-verify](https://github.com/online-judge-tools/verification-helper/blob/master/README.ja.md)を使って自動展開する前提でinclude文を使っていく

インクルードガードのため、`#pragma once`を全てつける

### Python
今のところはコピペなので、あまり多重にコピペする必要が生じないようにする
余裕ができたらツールほしい！

## テスト
oj-verifyとGitHub Actionsを使っての自動テストをするが、できない場合(Library Checker,yukicoder,AOJに言い問題がないなど)は提出リンクをコメントに貼る

## ドキュメント
C++はDoxygen
Pythonはdocstring
引数・戻り値くらいは型ヒント書く

## コーディング規約

using namespace std;
using ll = long long;

等は前提としない

## 作る人
基本的にはやりたい人が早いものがちでIssueをたてておく

決めとくもの
- グラフテンプレート: KowerKoint
- modint: ラクラムシ

Warning、最適化基準など

g++ -std=gnu++17 -I. -Wall -Wextra -O2 main.cpp