module AcLibraryRb
Constants
- HeapQueue
Priority Queue Reference: github.com/python/cpython/blob/master/Lib/heapq.py
- LazySegTree
Segment tree with Lazy propagation
- SegTree
Segment Tree
- TwoSat
TwoSAT
Reference: github.com/atcoder/ac-library/blob/master/atcoder/twosat.hpp- UnionFind
Disjoint Set Union
Public Instance Methods
# File lib_lock/ac-library-rb/inv_mod.rb, line 10 def _inv_gcd(a, b) a %= b # safe_mod s, t = b, a m0, m1 = 0, 1 while t > 0 u = s / t s -= t * u m0 -= m1 * u s, t = t, s m0, m1 = m1, m0 end m0 += b / s if m0 < 0 [s, m0] end
- EXPERIMENTAL
# File lib_lock/ac-library-rb/convolution.rb, line 128 def convolution(a, b, mod: 998244353, k: 35, z: 99) n = a.size m = b.size return [] if n == 0 || m == 0 raise ArgumentError if a.min < 0 || b.min < 0 format = "%0#{k}x" # "%024x" sa = "" sb = "" a.each{ |x| sa << (format % x) } b.each{ |x| sb << (format % x) } zero = '0' s = zero * z + ("%x" % (sa.hex * sb.hex)) i = -(n + m - 1) * k - 1 Array.new(n + m - 1){ (s[i + 1..i += k] || zero).hex % mod } end
return [rem, mod] or [0, 0] (if no solution)
# File lib_lock/ac-library-rb/crt.rb, line 3 def crt(r, m) unless r.size == m.size raise ArgumentError.new("size of r and m must be equal for crt(r, m)") end n = r.size r0, m0 = 0, 1 n.times do |i| raise ArgumentError if m[i] < 1 r1, m1 = r[i] % m[i], m[i] if m0 < m1 r0, r1 = r1, r0 m0, m1 = m1, m0 end if m0 % m1 == 0 return [0, 0] if r0 % m1 != r1 next end g, im = inv_gcd(m0, m1) u1 = m1 / g return [0, 0] if (r1 - r0) % g != 0 x = (r1 - r0) / g * im % u1 r0 += x * m0 m0 *= u1 r0 += m0 if r0 < 0 end return [r0, m0] end
# File lib_lock/ac-library-rb/floor_sum.rb, line 2 def floor_sum(n, m, a, b) raise ArgumentError if n < 0 || m < 1 res = 0 if a < 0 a2 = a % m res -= n * (n - 1) / 2 * ((a2 - a) / m) a = a2 end if b < 0 b2 = b % m res -= n * ((b2 - b) / m) b = b2 end res + floor_sum_unsigned(n, m, a, b) end
# File lib_lock/ac-library-rb/floor_sum.rb, line 22 def floor_sum_unsigned(n, m, a, b) res = 0 while true if a >= m res += n * (n - 1) / 2 * (a / m) a %= m end if b >= m res += n * (b / m) b %= m end y_max = a * n + b break if y_max < m n = y_max / m b = y_max % m m, a = a, m end res end
internal method return [g, x] s.t. g = gcd(a, b), x*a = g (mod b), 0 <= x < b/g
# File lib_lock/ac-library-rb/crt.rb, line 40 def inv_gcd(a, b) a %= b return [b, 0] if a == 0 s, t = b, a m0, m1 = 0, 1 while t > 0 u, s = s.divmod(t) m0 -= m1 * u s, t = t, s m0, m1 = m1, m0 end m0 += b / s if m0 < 0 return [s, m0] end
Use `x.pow(m - 2, m)` instead of `inv_mod(x, m)` if m is a prime number.
# File lib_lock/ac-library-rb/inv_mod.rb, line 3 def inv_mod(x, m) z = _inv_gcd(x, m) raise ArgumentError unless z.first == 1 z[1] end
lcp array for array of integers or string
# File lib_lock/ac-library-rb/lcp_array.rb, line 3 def lcp_array(s, sa) s = s.bytes if s.is_a?(String) n = s.size rnk = [0] * n sa.each_with_index{ |sa, id| rnk[sa] = id } lcp = [0] * (n - 1) h = 0 n.times{ |i| h -= 1 if h > 0 next if rnk[i] == 0 j = sa[rnk[i] - 1] h += 1 while j + h < n && i + h < n && s[j + h] == s[i + h] lcp[rnk[i] - 1] = h } return lcp end
Use `Integer#pow` unless m == 1
# File lib_lock/ac-library-rb/pow_mod.rb, line 3 def pow_mod(x, n, m) return 0 if m == 1 r, y = 1, x % m while n > 0 r = r * y % m if n.odd? y = y * y % m n >>= 1 end r end
SA-IS (internal method)
# File lib_lock/ac-library-rb/suffix_array.rb, line 37 def sa_is(s, upper) n = s.size return [] if n == 0 return [0] if n == 1 ls = [false] * n (n - 2).downto(0){ |i| ls[i] = (s[i] == s[i + 1] ? ls[i + 1] : s[i] < s[i + 1]) } sum_l = [0] * (upper + 1) sum_s = [0] * (upper + 1) n.times{ |i| if ls[i] sum_l[s[i] + 1] += 1 else sum_s[s[i]] += 1 end } 0.upto(upper){ |i| sum_s[i] += sum_l[i] sum_l[i + 1] += sum_s[i] if i < upper } lms = (1 ... n).select{ |i| !ls[i - 1] && ls[i] } m = lms.size lms_map = [-1] * (n + 1) lms.each_with_index{ |lms, id| lms_map[lms] = id } sa = sa_is_induce(s, ls, sum_l, sum_s, lms) return sa if m == 0 sorted_lms = sa.select{ |sa| lms_map[sa] != -1 } rec_s = [0] * m rec_upper = 0 rec_s[lms_map[sorted_lms[0]]] = 0 1.upto(m - 1) do |i| l, r = sorted_lms[i - 1, 2] end_l = lms[lms_map[l] + 1] || n end_r = lms[lms_map[r] + 1] || n same = true if end_l - l == end_r - r while l < end_l break if s[l] != s[r] l += 1 r += 1 end same = false if l == n || s[l] != s[r] else same = false end rec_upper += 1 if not same rec_s[lms_map[sorted_lms[i]]] = rec_upper end sa_is(rec_s, rec_upper).each_with_index{ |rec_sa, id| sorted_lms[id] = lms[rec_sa] } return sa_is_induce(s, ls, sum_l, sum_s, sorted_lms) end
induce sort (internal method)
# File lib_lock/ac-library-rb/suffix_array.rb, line 3 def sa_is_induce(s, ls, sum_l, sum_s, lms) n = s.size sa = [-1] * n buf = sum_s.dup lms.each{ |lms| if lms != n sa[buf[s[lms]]] = lms buf[s[lms]] += 1 end } buf = sum_l.dup sa[buf[s[-1]]] = n - 1 buf[s[-1]] += 1 sa.each{ |v| if v >= 1 && !ls[v - 1] sa[buf[s[v - 1]]] = v - 1 buf[s[v - 1]] += 1 end } buf = sum_l.dup sa.reverse_each{ |v| if v >= 1 && ls[v - 1] buf[s[v - 1] + 1] -= 1 sa[buf[s[v - 1] + 1]] = v - 1 end } return sa end
suffix array for array of integers or string
# File lib_lock/ac-library-rb/suffix_array.rb, line 103 def suffix_array(s, upper = nil) if upper s.each{ |s| raise ArgumentError if s < 0 || upper < s } else case s when Array # compression n = s.size idx = (0 ... n).sort_by{ |i| s[i] } t = [0] * n upper = 0 t[idx[0]] = 0 1.upto(n - 1){ |i| upper += 1 if s[idx[i - 1]] != s[idx[i]] t[idx[i]] = upper } s = t when String upper = 255 s = s.bytes end end return sa_is(s, upper) end
this implementation is different from ACL because of calculation time ref : snuke.hatenablog.com/entry/2014/12/03/214243 ACL implementation : atcoder.jp/contests/abc135/submissions/18836384 (731ms) this implementation : atcoder.jp/contests/abc135/submissions/18836378 (525ms)
# File lib_lock/ac-library-rb/z_algorithm.rb, line 7 def z_algorithm(s) n = s.size return [] if n == 0 s = s.codepoints if s.is_a?(String) z = [0] * n z[0] = n i, j = 1, 0 while i < n j += 1 while i + j < n && s[j] == s[i + j] z[i] = j if j == 0 i += 1 next end k = 1 while i + k < n && k + z[k] < j z[i + k] = z[k] k += 1 end i += k j -= k end return z end