search

yosupo06 / library-checker-problems

The problem data (Test case generator, judge's solution, task, ...) of Library Checker
https://judge.yosupo.jp/
Apache License 2.0
525 stars 120 forks source link

チェックしたいライブラリ #3

Open yosupo06 opened 5 years ago

yosupo06 commented 5 years ago

随時募集中

はガンガンresolvedにしていきます

yosupo06 commented 5 years ago

multipoint evaluation

yosupo06 commented 5 years ago

多項式補完

yosupo06 commented 5 years ago

2SAT

yosupo06 commented 5 years ago

suffix automoaton

yosupo06 commented 5 years ago

連立方程式の解(自由度あり)

yosupo06 commented 5 years ago

CHT

yosupo06 commented 5 years ago

Wavelet Tree / Matrix

yosupo06 commented 5 years ago

LC Tree

yosupo06 commented 5 years ago

Top Tree

yosupo06 commented 5 years ago

漸化式が与えられるからk番目

yosupo06 commented 5 years ago

Berlekamp massey

yosupo06 commented 5 years ago

Dinic

yosupo06 commented 5 years ago

mincostflow

yosupo06 commented 5 years ago

オイラー路

yosupo06 commented 5 years ago

lexbfs系？

yosupo06 commented 5 years ago

指数系？(max clique / 3 sat ...)

yosupo06 commented 5 years ago

n C k % m

yosupo06 commented 5 years ago

分割数

hos-lyric commented 5 years ago

F_p 上の多項式の因数分解

hos-lyric commented 5 years ago

convolution mod 一般 (or mod なし) mod 2^64 も

hos-lyric commented 5 years ago

F_p 上の多項式 (形式的冪級数) 各種演算 (除算とか合成とか exp とか) (チェックしたいライブラリといいつつ持ってなくてごめんなさい)

hos-lyric commented 5 years ago

f: 高々 d 次の多項式 f(0), ..., f(d) と a が与えられるので \sum_{0<=i<n} a^i f(i) を求めるやつ

hos-lyric commented 5 years ago

最大マッチング 最大重みマッチング (ちゃんとしたのを持っているとは言っていない) (ちゃんとしてないのを落とすのつらそう)

yosupo06 commented 5 years ago

nimber product

yosupo06 commented 5 years ago

帯行列の掃き出し(ちょいちょいみる)

hos-lyric commented 5 years ago

f: 高々 d 次の多項式 (given) \sum_{0<=i<INF} a^i f(i) を求めるやつ (-1 < a < 1 な有理数ということにして結果を mod とかで)

O(d^2) か，単項式にして O(d log d) をするか

latte0119 commented 5 years ago

ベルヌーイ数 mod 998244353 の先頭n項 (n<=1e5) 形式的冪級数x/(exp(x)-1)を計算する

hos-lyric commented 5 years ago

連立一次合同式 a_i x == b_i (mod m_i) を解く (x == b (mod m) にする)

a_i = 1 でもいいかもしれない

yosupo06 commented 5 years ago

任意(非素数)modでの行列式

kmyk commented 5 years ago

点更新 + 非可換な演算 (行列の積とか) に関する区間積

セグメント木の非再帰実装は可換性のまわりでバグりやすいのに、RMQ や RSQ だとそこがテストできないので

kmyk commented 5 years ago

重軽分解 + セグメント木で木上のパスクエリを処理するやつ

頂点クエリの場合と辺クエリの場合が両方ほしいです

yosupo06 commented 5 years ago

重心分解

yosupo06 commented 5 years ago

オンラインのFFT、分割統治していくやつ

hec12 commented 5 years ago

Aho-Corasick

beet-aizu commented 5 years ago

Grith (Minimum Cycle)

beet-aizu commented 5 years ago

最大独立安定集合

beet-aizu commented 5 years ago

一般マッチング

beet-aizu commented 5 years ago

グラフの彩色数

beet-aizu commented 5 years ago

最小流量制約付き最大流

beet-aizu commented 5 years ago

負辺を含む最小費用流

beet-aizu commented 5 years ago

Binary Trie

beet-aizu commented 5 years ago

回文木（これいる？）

beet-aizu commented 5 years ago

長さ N の広義単調増加列で和が M 以下のものの数 https://twitter.com/maroon_kuri/status/1171708639914029057?s=20

beet-aizu commented 5 years ago

離散対数

yosupo06 commented 5 years ago

木に頂点クエリが飛んでくるから本質の頂点だけに圧縮するやつ

yosupo06 commented 5 years ago

離散対数

28

hec12 commented 5 years ago

無向グラフの全域カット

hec12 commented 5 years ago

最小シュタイナー木

hos-lyric commented 5 years ago

素数篩 (10^8 とか 10^9 とかまでやると，出力形式がむずかしいね)

beet-aizu commented 5 years ago

グラフの中の三角形の個数　O(M sqrt(M)) https://www.slideshare.net/catupper/trianguler