Nyaan's Library

This documentation is automatically generated by online-judge-tools/verification-helper

View on GitHub

:heavy_check_mark: string/number-of-subsequences.hpp

Depends on

Verified with

Code

#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;
}
Back to top page