distinct_subsequences.hpp¶
Count distinct nonempty subsequences over an arbitrary modular field.
Verified by number_of_subsequences.
\[
\displaystyle |\\{\text{subseq}(s)\\}|_{\neq\emptyset}
\]
Implementation¶
#ifndef NOYA_DISTINCT_SUBSEQUENCES_HPP
#define NOYA_DISTINCT_SUBSEQUENCES_HPP 1
/// @complexity Time: O(n log n).
/// Space: O(n).
#include <algorithm>
#include <vector>
namespace noya {
/// @brief Count distinct nonempty subsequences over an arbitrary modular field.
template <class Mint, class T>
Mint distinct_subsequence_count(const std::vector<T> &values) {
std::vector<T> coordinates = values;
std::sort(coordinates.begin(), coordinates.end());
coordinates.erase(std::unique(coordinates.begin(), coordinates.end()),
coordinates.end());
std::vector<Mint> previous(coordinates.size());
Mint total = 1; // The empty subsequence.
for (const T &value : values) {
int id = int(std::lower_bound(coordinates.begin(), coordinates.end(), value) -
coordinates.begin());
Mint old_total = total;
total += total - previous[id];
previous[id] = old_total;
}
return total - Mint(1);
}
} // namespace noya
#endif // NOYA_DISTINCT_SUBSEQUENCES_HPP
#include <algorithm>
#include <vector>
/// @complexity Time: O(n log n).
/// Space: O(n).
namespace noya {
/// @brief Count distinct nonempty subsequences over an arbitrary modular field.
template <class Mint, class T>
Mint distinct_subsequence_count(const std::vector<T> &values) {
std::vector<T> coordinates = values;
std::sort(coordinates.begin(), coordinates.end());
coordinates.erase(std::unique(coordinates.begin(), coordinates.end()),
coordinates.end());
std::vector<Mint> previous(coordinates.size());
Mint total = 1; // The empty subsequence.
for (const T &value : values) {
int id = int(std::lower_bound(coordinates.begin(), coordinates.end(), value) -
coordinates.begin());
Mint old_total = total;
total += total - previous[id];
previous[id] = old_total;
}
return total - Mint(1);
}
} // namespace noya