Top Level Namespace
Defined Under Namespace
Modules: AcLibraryRb Classes: Array, Convolution, DSU, Deque, FenwickTree, Integer, LazySegtree, MaxFlow, MinCostFlow, ModInt, PriorityQueue, SCC, Segtree, String, TwoSAT
Constant Summary collapse
- UnionFind =
DSU
- SegTree =
Segtree
- TwoSat =
TwoSAT
- LazySegTree =
LazySegtree
- HeapQueue =
PriorityQueue
Instance Method Summary collapse
- #_inv_gcd(a, b) ⇒ Object
-
#convolution(a, b, mod: 998_244_353, k: 35, z: 99) ⇒ Object
[EXPERIMENTAL].
-
#crt(r, m) ⇒ Object
return [rem, mod] or [0, 0] (if no solution).
- #floor_sum(n, m, a, b) ⇒ Object
- #floor_sum_unsigned(n, m, a, b) ⇒ Object
-
#inv_gcd(a, b) ⇒ Object
internal method return [g, x] s.t.
-
#inv_mod(x, m) ⇒ Object
Use ‘x.pow(m - 2, m)` instead of `inv_mod(x, m)` if m is a prime number.
-
#lcp_array(s, sa) ⇒ Object
lcp array for array of integers or string.
- #ModInt(val) ⇒ Object
-
#pow_mod(x, n, m) ⇒ Object
Use ‘Integer#pow` unless m == 1.
-
#sa_is(s, upper) ⇒ Object
SA-IS (internal method).
-
#sa_is_induce(s, ls, sum_l, sum_s, lms) ⇒ Object
induce sort (internal method).
-
#suffix_array(s, upper = nil) ⇒ Object
suffix array for array of integers or string.
-
#z_algorithm(s) ⇒ Object
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).
Instance Method Details
#_inv_gcd(a, b) ⇒ Object
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
# File 'lib/inv_mod.rb', line 9 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 |
#convolution(a, b, mod: 998_244_353, k: 35, z: 99) ⇒ Object
- EXPERIMENTAL
127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 |
# File 'lib/convolution.rb', line 127 def convolution(a, b, mod: 998_244_353, 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 |
#crt(r, m) ⇒ Object
return [rem, mod] or [0, 0] (if no solution)
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
# File 'lib/crt.rb', line 2 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 |
#floor_sum(n, m, a, b) ⇒ Object
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
# File 'lib/floor_sum.rb', line 1 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 |
#floor_sum_unsigned(n, m, a, b) ⇒ Object
21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
# File 'lib/floor_sum.rb', line 21 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 |
#inv_gcd(a, b) ⇒ Object
internal method return [g, x] s.t. g = gcd(a, b), x*a = g (mod b), 0 <= x < b/g
39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
# File 'lib/crt.rb', line 39 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 |
#inv_mod(x, m) ⇒ Object
Use ‘x.pow(m - 2, m)` instead of `inv_mod(x, m)` if m is a prime number.
2 3 4 5 6 7 |
# File 'lib/inv_mod.rb', line 2 def inv_mod(x, m) z = _inv_gcd(x, m) raise ArgumentError unless z.first == 1 z[1] end |
#lcp_array(s, sa) ⇒ Object
lcp array for array of integers or string
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
# File 'lib/lcp_array.rb', line 2 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 |
#ModInt(val) ⇒ Object
1 2 3 |
# File 'lib/core_ext/modint.rb', line 1 def ModInt(val) ModInt.new(val) end |
#pow_mod(x, n, m) ⇒ Object
Use ‘Integer#pow` unless m == 1
2 3 4 5 6 7 8 9 10 11 12 13 |
# File 'lib/pow_mod.rb', line 2 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(s, upper) ⇒ Object
SA-IS (internal method)
36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 |
# File 'lib/suffix_array.rb', line 36 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 |
#sa_is_induce(s, ls, sum_l, sum_s, lms) ⇒ Object
induce sort (internal method)
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
# File 'lib/suffix_array.rb', line 2 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(s, upper = nil) ⇒ Object
suffix array for array of integers or string
102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 |
# File 'lib/suffix_array.rb', line 102 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 |
#z_algorithm(s) ⇒ Object
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)
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
# File 'lib/z_algorithm.rb', line 6 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 |