issues
search
boj-rs
/
basm-rs
Rust 코드를 컴파일한 후 실행 파일을 온라인 채점 환경에 제출할 수 있도록 변환합니다.
Other
108
stars
12
forks
source link
NTT: add polyinv/div/mod and polyeval
#73
Closed
byeongkeunahn
closed
9 months ago
byeongkeunahn
commented
9 months ago
Polynomial inverse/division/modulo: implemented to be
O(n lg n)
using Hensel lifting (Newton method)
Polynomial evaluation: implemented to be
O(n lg^2 n)
using multipoint evaluation by divide-and-conquer, as explained in
https://codeforces.com/blog/entry/100279
and
https://cr.yp.to/arith/scaledmod-20040820.pdf
.
O(n lg n)using Hensel lifting (Newton method)O(n lg^2 n)using multipoint evaluation by divide-and-conquer, as explained in https://codeforces.com/blog/entry/100279 and https://cr.yp.to/arith/scaledmod-20040820.pdf.