体を並列に扱う ($K_1\times K_2\times\cdots\times K_n$) (src/Misc/Pointwise.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-02-05 22:57:52+09:00
• Include: #include "src/Misc/Pointwise.hpp"

Rolling Hash などのハッシュ計算をする時に, baseを変えたパターンのを並行して扱うのを便利にするために作った.

Verify

• AtCoder Regular Contest 099 F - Eating Symbols Hard(多項式ハッシュ)
• 第二回全国統一プログラミング王決定戦本戦 D - 木、 (根付き木ハッシュ)

Verified with

• test/aoj/0322.RH.test.cpp
• test/aoj/0355.test.cpp
• test/aoj/2614.RH.test.cpp
• test/aoj/2711.RH.test.cpp
• test/aoj/2763.RH.test.cpp
• test/aoj/ALDS1_14_B.RH.test.cpp
• test/atcoder/abc135_f.RH.test.cpp
• test/atcoder/abc141_e.RH.test.cpp
• test/atcoder/abc272_f.RH.test.cpp
• test/atcoder/abc274_ex.test.cpp
• test/atcoder/agc047_b.RH.test.cpp
• test/hackerrank/morgan-and-a-string.RH.test.cpp
• test/hackerrank/save-humanity.RH.test.cpp
• test/loj/2072.test.cpp
• test/loj/2192.test.cpp
• test/yosupo/enumerate_palindromes.RH.test.cpp
• test/yosupo/rooted_tree_isomorphism_classification.test.cpp
• test/yosupo/z_algorithm.RH.test.cpp
• test/yukicoder/2332.RH.test.cpp
• test/yukicoder/2454.RH.test.cpp
• test/yukicoder/599.RH.test.cpp
• test/yukicoder/765.RH.test.cpp

Code

#pragma once
#include <tuple>
#include <array>
#include <utility>
template <class... Ks> struct Pointwise: std::tuple<Ks...> {
 static constexpr int N= sizeof...(Ks);
 using Self= Pointwise;
 using std::tuple<Ks...>::tuple;
 template <class T> Pointwise(const T &v) { fill(v, std::make_index_sequence<N>()); }
 template <class T, std::size_t... I> std::array<int, N> fill(const T &v, std::index_sequence<I...>) { return {{(void(std::get<I>(*this)= v), 0)...}}; }
#define HELPER(name, op) \
 template <std::size_t... I> std::array<int, N> name(const Self &y, std::index_sequence<I...>) { return {{(void(std::get<I>(*this) op##= std::get<I>(y)), 0)...}}; } \
 Self &operator op##=(const Self & r) { return name(r, std::make_index_sequence<N>()), *this; }
 HELPER(add_assign, +)
 HELPER(dif_assign, -)
 HELPER(mul_assign, *)
 HELPER(div_assign, /)
#undef HELPER
 Self operator+(const Self &r) const { return Self(*this)+= r; }
 Self operator-(const Self &r) const { return Self(*this)-= r; }
 Self operator*(const Self &r) const { return Self(*this)*= r; }
 Self operator/(const Self &r) const { return Self(*this)/= r; }
};

#line 2 "src/Misc/Pointwise.hpp"
#include <tuple>
#include <array>
#include <utility>
template <class... Ks> struct Pointwise: std::tuple<Ks...> {
 static constexpr int N= sizeof...(Ks);
 using Self= Pointwise;
 using std::tuple<Ks...>::tuple;
 template <class T> Pointwise(const T &v) { fill(v, std::make_index_sequence<N>()); }
 template <class T, std::size_t... I> std::array<int, N> fill(const T &v, std::index_sequence<I...>) { return {{(void(std::get<I>(*this)= v), 0)...}}; }
#define HELPER(name, op) \
 template <std::size_t... I> std::array<int, N> name(const Self &y, std::index_sequence<I...>) { return {{(void(std::get<I>(*this) op##= std::get<I>(y)), 0)...}}; } \
 Self &operator op##=(const Self & r) { return name(r, std::make_index_sequence<N>()), *this; }
 HELPER(add_assign, +)
 HELPER(dif_assign, -)
 HELPER(mul_assign, *)
 HELPER(div_assign, /)
#undef HELPER
 Self operator+(const Self &r) const { return Self(*this)+= r; }
 Self operator-(const Self &r) const { return Self(*this)-= r; }
 Self operator*(const Self &r) const { return Self(*this)*= r; }
 Self operator/(const Self &r) const { return Self(*this)/= r; }
};

Back to top page