DP/cnt_distinct_subseq.h

• View this file on GitHub
• Last update: 2022-12-26 18:08:50+08:00

Depends on

• Misc/compress.h

Verified with

• DP/tests/yosupo_cnt_distinct_subseq.test.cpp

Code

#include "../Misc/compress.h"

// Returns number of distinct, non-empty subsequences {{{
// T = type of input elements
// OutT = type of output (e.g. ModInt)
template<typename T, typename OutT>
OutT cnt_distinct_subsequences(std::vector<T> a) {
    auto compressor = CompressorBuilder<T>{a}.build();
    compressor.compress_inplace(a);

    std::vector<OutT> f(a.size() + 1);
    std::vector<int> last(a.size() + 1, -1);
    f[0] = 1;
    for (size_t i = 0; i < a.size(); ++i) {
        f[i+1] = f[i] * 2;
        if (last[a[i]] >= 0) f[i+1] -= f[last[a[i]]];
        last[a[i]] = i;
    }
    return f.back() - 1;
}
// }}}

#line 1 "Misc/compress.h"
// Compressor {{{
/* Example usage:
    auto compressor = CompressorBuilder<T>{vs}.build();
    int x = compessor.must_eq(vs[0]);
    compressor.compress_inplace(vs);
*/
// Based on https://suisen-cp.github.io/cp-library-cpp/library/util/coordinate_compressor.hpp
template<typename T>
struct CompressorBuilder {
    // Do not use directly. Use builder.build()
    struct Compressor {
        // Number of unique keys
        int size() const { return xs.size(); }

        void compress_inplace(std::vector<T>& vals) {
            for (int& val : vals) {
                val = must_eq(val);
            }
        }

        [[nodiscard]] std::vector<T> compress(const std::vector<T>& vals) {
            std::vector<T> res(vals.size());
            for (int i = 0; i < static_cast<int> (res.size()); ++i) {
                res[i] = must_eq(vals[i]);
            }
            return res;
        }

        bool has_key(const T& key) const {
            return std::binary_search(xs.begin(), xs.end(), key);
        }

#define LB(key) std::lower_bound(xs.begin(), xs.end(), key)
#define UB(key) std::upper_bound(xs.begin(), xs.end(), key)
        std::optional<int> eq(const T& key) {
            auto it = LB(key);
            return it == xs.end() ? std::nullopt : std::optional<int>{it - xs.begin()};
        }
        std::optional<int> geq(const T& key) {
            auto it = LB(key);
            return it == xs.end() ? std::nullopt : std::optional<int>{it - xs.begin()};
        }
        std::optional<int> gt(const T& key) {
            auto it = UB(key);
            return it == xs.end() ? std::nullopt : std::optional<int>{it - xs.begin()};
        }
        std::optional<int> leq(const T& key) {
            auto it = UB(key);
            return it == xs.begin() ? std::nullopt : std::optional<int>{it - xs.begin() - 1};
        }
        std::optional<int> lt(const T& key) {
            auto it = LB(key);
            return it == xs.begin() ? std::nullopt : std::optional<int>{it - xs.begin() - 1};
        }

        // throw exception if no such key is found
        int must_eq(const T& key) {
            auto it = LB(key);
            assert(it != xs.end());
            return it - xs.begin();
        }
        // throw exception if no such key is found
        int must_geq(const T& key) {
            auto it = LB(key);
            assert(it != xs.end());
            return it - xs.begin();
        }
        // throw exception if no such key is found
        int must_gt(const T& key) {
            auto it = UB(key);
            assert(it != xs.end());
            return it - xs.begin();
        }
        // throw exception if no such key is found
        int must_leq(const T& key) {
            auto it = UB(key);
            assert(it != xs.begin());
            return it - xs.begin() - 1;
        }
        // throw exception if no such key is found
        int must_lt(const T& key) {
            auto it = LB(key);
            assert(it != xs.begin());
            return it - xs.begin() - 1;
        }
#undef LB
#undef UB

        std::vector<T> xs;
    };

    auto build() {
        std::sort(xs.begin(), xs.end());
        xs.erase(std::unique(xs.begin(), xs.end()), xs.end());
        return Compressor{xs};
    }

    void add(const T& key) { xs.push_back(key); }
    void add(T&& key) { xs.push_back(std::move(key)); }

    std::vector<T> xs;
};
// }}}
#line 2 "DP/cnt_distinct_subseq.h"

// Returns number of distinct, non-empty subsequences {{{
// T = type of input elements
// OutT = type of output (e.g. ModInt)
template<typename T, typename OutT>
OutT cnt_distinct_subsequences(std::vector<T> a) {
    auto compressor = CompressorBuilder<T>{a}.build();
    compressor.compress_inplace(a);

    std::vector<OutT> f(a.size() + 1);
    std::vector<int> last(a.size() + 1, -1);
    f[0] = 1;
    for (size_t i = 0; i < a.size(); ++i) {
        f[i+1] = f[i] * 2;
        if (last[a[i]] >= 0) f[i+1] -= f[last[a[i]]];
        last[a[i]] = i;
    }
    return f.back() - 1;
}
// }}}

Back to top page