Number of Subsequences
(algo/sequence/number_of_subsequences.hpp)

• View this file on GitHub
• Last update: 2026-07-10 18:48:41+09:00
• Include: #include "algo/sequence/number_of_subsequences.hpp"

Overview

number_of_distinct_subsequences counts the distinct nonempty subsequences of a sequence. Two subsequences are considered equal when their value sequences are equal, even if they use different source indices.

For example, [1, 1] has two distinct nonempty subsequences: [1] and [1, 1].

The dynamic program maintains the number of distinct subsequences including the empty sequence. Appending a value initially doubles that number. The subsequences already created when the same value last appeared are subtracted to remove duplicates.

Requirements

T must support < as a strict weak ordering. Mint must be constructible from integers and support addition and subtraction. It is normally a modular integer type such as m1une::math::ModInt<998244353>.

Interface

Function	Complexity	Description
Mint number_of_distinct_subsequences<Mint>(const std::vector<T>& values)	$O(N\log N)$ time and $O(N)$ memory	Counts distinct nonempty subsequences.
Mint number_of_subsequences<Mint>(const std::vector<T>& values)	$O(N\log N)$ time and $O(N)$ memory	Alias matching the Library Checker problem name.

The empty input has zero nonempty subsequences. The input vector is not modified.

Example

#include "algo/sequence/number_of_subsequences.hpp"
#include "math/modint.hpp"

#include <iostream>
#include <vector>

int main() {
    using Mint = m1une::math::ModInt<998244353>;
    std::vector<int> values = {1, 2, 1};

    Mint answer = m1une::algo::number_of_subsequences<Mint>(values);
    std::cout << answer << "\n"; // 6
}

Required by

• Algorithms All (algo/all.hpp)
• Sequence Algorithms All (algo/sequence/all.hpp)

Verified with

• verify/algo/sequence/number_of_subsequences.test.cpp

Code

#ifndef M1UNE_ALGO_SEQUENCE_NUMBER_OF_SUBSEQUENCES_HPP
#define M1UNE_ALGO_SEQUENCE_NUMBER_OF_SUBSEQUENCES_HPP 1

#include <algorithm>
#include <vector>

namespace m1une {
namespace algo {

// Returns the number of distinct nonempty subsequences.
template <class Mint, class T>
Mint number_of_distinct_subsequences(const std::vector<T>& values) {
    std::vector<T> compressed = values;
    std::sort(compressed.begin(), compressed.end());
    compressed.erase(
        std::unique(compressed.begin(), compressed.end()),
        compressed.end()
    );

    std::vector<Mint> previous_total(compressed.size(), Mint(0));
    Mint total = 1;
    for (const T& value : values) {
        int rank = int(
            std::lower_bound(
                compressed.begin(),
                compressed.end(),
                value
            ) - compressed.begin()
        );
        Mint old_total = total;
        total = total + total - previous_total[rank];
        previous_total[rank] = old_total;
    }
    return total - Mint(1);
}

template <class Mint, class T>
Mint number_of_subsequences(const std::vector<T>& values) {
    return number_of_distinct_subsequences<Mint>(values);
}

}  // namespace algo
}  // namespace m1une

#endif  // M1UNE_ALGO_SEQUENCE_NUMBER_OF_SUBSEQUENCES_HPP

#line 1 "algo/sequence/number_of_subsequences.hpp"



#include <algorithm>
#include <vector>

namespace m1une {
namespace algo {

// Returns the number of distinct nonempty subsequences.
template <class Mint, class T>
Mint number_of_distinct_subsequences(const std::vector<T>& values) {
    std::vector<T> compressed = values;
    std::sort(compressed.begin(), compressed.end());
    compressed.erase(
        std::unique(compressed.begin(), compressed.end()),
        compressed.end()
    );

    std::vector<Mint> previous_total(compressed.size(), Mint(0));
    Mint total = 1;
    for (const T& value : values) {
        int rank = int(
            std::lower_bound(
                compressed.begin(),
                compressed.end(),
                value
            ) - compressed.begin()
        );
        Mint old_total = total;
        total = total + total - previous_total[rank];
        previous_total[rank] = old_total;
    }
    return total - Mint(1);
}

template <class Mint, class T>
Mint number_of_subsequences(const std::vector<T>& values) {
    return number_of_distinct_subsequences<Mint>(values);
}

}  // namespace algo
}  // namespace m1une

Back to top page