#include "string/number-of-subsequences.hpp"
#pragma once #include "../hashmap/hashmap-unerasable.hpp" template <typename Container, typename mint> mint number_of_subsequences(const Container& S) { using Key = typename Container::value_type; UnerasableHashMap<Key, mint> mp; mint al = 1; for (auto& c : S) { mint& mpc = mp[c]; mint x = mpc; mpc = al; al += al - x; } return al - 1; }
#line 2 "string/number-of-subsequences.hpp" #line 2 "hashmap/hashmap-unerasable.hpp" #include <cassert> #include <chrono> #include <functional> #include <vector> using namespace std; #line 2 "internal/internal-hash-function.hpp" #line 4 "internal/internal-hash-function.hpp" using namespace std; #line 2 "internal/internal-seed.hpp" #line 4 "internal/internal-seed.hpp" using namespace std; namespace internal { unsigned long long non_deterministic_seed() { unsigned long long m = chrono::duration_cast<chrono::nanoseconds>( chrono::high_resolution_clock::now().time_since_epoch()) .count(); m ^= 9845834732710364265uLL; m ^= m << 24, m ^= m >> 31, m ^= m << 35; return m; } unsigned long long deterministic_seed() { return 88172645463325252UL; } // 64 bit の seed 値を生成 (手元では seed 固定) // 連続で呼び出すと同じ値が何度も返ってくるので注意 // #define RANDOMIZED_SEED するとシードがランダムになる unsigned long long seed() { #if defined(NyaanLocal) && !defined(RANDOMIZED_SEED) return deterministic_seed(); #else return non_deterministic_seed(); #endif } } // namespace internal #line 2 "internal/internal-type-traits.hpp" #include <type_traits> using namespace std; namespace internal { template <typename T> using is_broadly_integral = typename conditional_t<is_integral_v<T> || is_same_v<T, __int128_t> || is_same_v<T, __uint128_t>, true_type, false_type>::type; template <typename T> using is_broadly_signed = typename conditional_t<is_signed_v<T> || is_same_v<T, __int128_t>, true_type, false_type>::type; template <typename T> using is_broadly_unsigned = typename conditional_t<is_unsigned_v<T> || is_same_v<T, __uint128_t>, true_type, false_type>::type; #define ENABLE_VALUE(x) \ template <typename T> \ constexpr bool x##_v = x<T>::value; ENABLE_VALUE(is_broadly_integral); ENABLE_VALUE(is_broadly_signed); ENABLE_VALUE(is_broadly_unsigned); #undef ENABLE_VALUE #define ENABLE_HAS_TYPE(var) \ template <class, class = void> \ struct has_##var : false_type {}; \ template <class T> \ struct has_##var<T, void_t<typename T::var>> : true_type {}; \ template <class T> \ constexpr auto has_##var##_v = has_##var<T>::value; #define ENABLE_HAS_VAR(var) \ template <class, class = void> \ struct has_##var : false_type {}; \ template <class T> \ struct has_##var<T, void_t<decltype(T::var)>> : true_type {}; \ template <class T> \ constexpr auto has_##var##_v = has_##var<T>::value; } // namespace internal #line 8 "internal/internal-hash-function.hpp" namespace internal { // 整数, 整数列を 64 bit unsigned int へ移す using u64 = unsigned long long; using u128 = __uint128_t; ENABLE_HAS_TYPE(first_type); ENABLE_HAS_TYPE(second_type); ENABLE_HAS_TYPE(iterator); template <typename T> u64 hash_function(const T& x) { static u64 r = seed(); constexpr u64 z1 = 11995408973635179863ULL; if constexpr (is_broadly_integral_v<T>) { // Integral return (u64(x) ^ r) * z1; } else if constexpr (has_first_type_v<T> && has_second_type_v<T>) { // pair constexpr u64 z2 = 10150724397891781847ULL; return hash_function(x.first) + hash_function(x.second) * z2; } else if constexpr (has_iterator_v<T>) { // Container constexpr u64 mod = (1LL << 61) - 1; constexpr u64 base = 950699498548472943ULL; u64 m = 0; for (auto& z : x) { u64 w; if constexpr (is_broadly_integral_v<T>) { w = u64(z) ^ r; } else { w = hash_function(z); } u128 y = u128(m) * base + (w & mod); m = (y & mod) + (y >> 61); if (m >= mod) m -= mod; } m ^= m << 24, m ^= m >> 31, m ^= m << 35; return m; } else { static_assert([]() { return false; }()); } } template <typename Key> struct HashObject { size_t operator()(const Key& x) const { return hash_function(x); } }; } // namespace internal /* @brief ハッシュ関数 */ #line 10 "hashmap/hashmap-unerasable.hpp" // 削除不可能な hashmap // // テンプレート引数 // fixed_size : これを true にするするとバケットサイズが固定になる // get_hash : ハッシュ関数の指定 // 引数 // _default_value : val の初期値, この値で初期化 // _default_size : // バケットサイズ, max(4, _default_size) 以上の 2 べきで初期化 // ただし fixed_size が true の時にしかサイズを変更できない template <typename Key, typename Val, bool fixed_size = false, unsigned long long (*get_hash)(const Key&) = internal::hash_function<Key>> struct UnerasableHashMap { int N, occupied_num, shift; vector<Key> keys; vector<Val> vals; vector<char> flag; Val default_value; int default_size; // サイズを n に変更する void init(int n, bool reset = false) { assert(n >= 4 && (n & (n - 1)) == 0); if constexpr (fixed_size) { assert(reset == true); n = N; } if (reset == true) { N = n, occupied_num = 0, shift = 64 - __builtin_ctz(n); keys.resize(n); vals.resize(n); flag.resize(n); fill(begin(vals), end(vals), default_value); fill(begin(flag), end(flag), 0); } else { N = n, shift = 64 - __builtin_ctz(n); vector<Key> keys2(n); vector<Val> vals2(n, default_value); vector<char> flag2(n); swap(keys, keys2), swap(vals, vals2), swap(flag, flag2); for (int i = 0; i < (int)flag2.size(); i++) { if (flag2[i]) { int j = hint(keys2[i]); keys[j] = keys2[i], vals[j] = vals2[i], flag[j] = 1; } } } } UnerasableHashMap(const Val& _default_value = Val{}, int _default_size = 4) : occupied_num(0), default_value(_default_value) { if (fixed_size == false) _default_size = 4; N = 4; while (N < _default_size) N *= 2; default_size = N; init(N, true); } int hint(const Key& k) { int hash = get_hash(k) >> shift; while (flag[hash] && keys[hash] != k) hash = (hash + 1) & (N - 1); return hash; } // key が i である要素への参照を返す Val& operator[](const Key& k) { int i = hint(k); if (!flag[i]) { if constexpr (fixed_size == false) { if (occupied_num * 2 >= N) { init(2 * N), i = hint(k); } } keys[i] = k, flag[i] = 1, occupied_num++; } return vals[i]; } Val get(const Key& k) { int i = hint(k); return flag[i] ? vals[i] : default_value; } // 走査, f に関数 f(key, val) を入れる template <typename F> void enumerate(const F f) { for (int i = 0; i < (int)flag.size(); i++) { if (flag[i]) f(keys[i], vals[i]); } } int count(const Key& k) { return flag[hint(k)]; } bool contain(const Key& k) { return flag[hint(k)]; } int size() const { return occupied_num; } void reset() { init(default_size, true); } void clear() { init(default_size, true); } }; #line 4 "string/number-of-subsequences.hpp" template <typename Container, typename mint> mint number_of_subsequences(const Container& S) { using Key = typename Container::value_type; UnerasableHashMap<Key, mint> mp; mint al = 1; for (auto& c : S) { mint& mpc = mp[c]; mint x = mpc; mpc = al; al += al - x; } return al - 1; }