test/src/dp/number_of_subsequences/number_of_subsequences.test.cpp

• View this file on GitHub
• Last update: 2022-07-26 15:37:13+09:00
• Problem: https://judge.yosupo.jp/problem/number_of_subsequences

Depends on

• Number Of Subsequences (library/dp/number_of_subsequences.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/number_of_subsequences"

#include <iostream>
#include <atcoder/modint>

#include "library/dp/number_of_subsequences.hpp"

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;

    std::vector<int> a(n);
    for (auto &e : a) std::cin >> e;

    std::cout << suisen::number_of_nonempty_subsequences<atcoder::modint998244353>(a).val() << '\n';

    return 0;
}

#line 1 "test/src/dp/number_of_subsequences/number_of_subsequences.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/number_of_subsequences"

#include <iostream>
#include <atcoder/modint>

#line 1 "library/dp/number_of_subsequences.hpp"



#include <algorithm>
#include <vector>

namespace suisen {
    // Requirement: T is comparable 
    template <typename Int, typename T>
    auto number_of_nonempty_subsequences(const std::vector<T> &a) -> decltype(std::declval<T>() < std::declval<T>(), Int{}) {
        const int n = a.size();
        std::vector<std::pair<T, int>> sorted(n);
        for (int i = 0; i < n; ++i) sorted[i] = { a[i], i };
        std::sort(sorted.begin(), sorted.end());

        std::vector<int> last(n, -1);
        for (int i = 0; i < n;) {
            for (auto [v, p] = sorted[i]; ++i < n and sorted[i].first == v;) {
                const int c = sorted[i].second;
                last[c] = std::exchange(p, c);
            }
        }

        std::vector<Int> sdp(n + 2);
        sdp[1] = 1;
        for (int i = 0; i < n; ++i) sdp[i + 2] = sdp[i + 1] + sdp[i + 1] - sdp[last[i] + 1];
        return sdp[n + 1] - 1;
    }
} // namespace suisen


#line 7 "test/src/dp/number_of_subsequences/number_of_subsequences.test.cpp"

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;

    std::vector<int> a(n);
    for (auto &e : a) std::cin >> e;

    std::cout << suisen::number_of_nonempty_subsequences<atcoder::modint998244353>(a).val() << '\n';

    return 0;
}

Back to top page