distinct_subsequences.hpp¶
统计序列的不同非空子序列数量；重复元素通过记录其上次贡献去重。
\[
\displaystyle |\\{\text{subseq}(s)\\}|_{\neq\emptyset}
\]
Complexity: Time: O(n log n). Space: O(n).
AC 记录：number_of_subsequences。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @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> &vs) {
std::vector<T> xs = vs;
std::sort(xs.begin(), xs.end());
xs.erase(std::unique(xs.begin(), xs.end()), xs.end());
std::vector<Mint> pre(xs.size());
Mint tot = 1; // The empty subsequence.
for (const T &val : vs) {
int id = int(std::lower_bound(xs.begin(), xs.end(), val) - xs.begin());
Mint ot = tot;
tot += tot - pre[id];
pre[id] = ot;
}
return tot - Mint(1);
}
} // namespace noya
#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> &vs) {
std::vector<T> xs = vs;
std::sort(xs.begin(), xs.end());
xs.erase(std::unique(xs.begin(), xs.end()), xs.end());
std::vector<Mint> pre(xs.size());
Mint tot = 1; // The empty subsequence.
for (const T &val : vs) {
int id = int(std::lower_bound(xs.begin(), xs.end(), val) - xs.begin());
Mint ot = tot;
tot += tot - pre[id];
pre[id] = ot;
}
return tot - 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> &vs) {
std::vector<T> xs = vs;
std::sort(xs.begin(), xs.end());
xs.erase(std::unique(xs.begin(), xs.end()), xs.end());
std::vector<Mint> pre(xs.size());
Mint tot = 1; // The empty subsequence.
for (const T &val : vs) {
int id = int(std::lower_bound(xs.begin(), xs.end(), val) - xs.begin());
Mint ot = tot;
tot += tot - pre[id];
pre[id] = ot;
}
return tot - Mint(1);
}
} // namespace noya