ACM_Notebook_new
This documentation is automatically generated by online-judge-tools/verification-helper
DP/tests/yosupo_cnt_distinct_subseq.test.cpp
- View this file on GitHub
- Last update: 2023-10-15 09:43:20+08:00
- Problem: https://judge.yosupo.jp/problem/number_of_subsequences
Depends on
Code
#define PROBLEM "https://judge.yosupo.jp/problem/number_of_subsequences"
#include "../../template.h"
#include "../cnt_distinct_subseq.h"
#include "../../Math/modint.h"
const int MOD = 998244353;
using mint = ModInt<MOD>;
void solve() {
int n; cin >> n;
vector<int> a(n);
REP(i,n) cin >> a[i];
cout << cnt_distinct_subsequences<int, mint> (a) << endl;
}#line 1 "DP/tests/yosupo_cnt_distinct_subseq.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/number_of_subsequences"
#line 1 "template.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define EACH(it,a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
#define DEBUG(x) { cout << #x << " = "; cout << (x) << endl; }
#define PR(a,n) { cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl; }
#define PR0(a,n) { cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl; }
#define sqr(x) ((x) * (x))
// For printing pair, container, etc.
// Copied from https://quangloc99.github.io/2021/07/30/my-CP-debugging-template.html
template<class U, class V> ostream& operator << (ostream& out, const pair<U, V>& p) {
return out << '(' << p.first << ", " << p.second << ')';
}
template<class Con, class = decltype(begin(declval<Con>()))>
typename enable_if<!is_same<Con, string>::value, ostream&>::type
operator << (ostream& out, const Con& con) {
out << '{';
for (auto beg = con.begin(), it = beg; it != con.end(); it++) {
out << (it == beg ? "" : ", ") << *it;
}
return out << '}';
}
template<size_t i, class T> ostream& print_tuple_utils(ostream& out, const T& tup) {
if constexpr(i == tuple_size<T>::value) return out << ")";
else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup);
}
template<class ...U> ostream& operator << (ostream& out, const tuple<U...>& t) {
return print_tuple_utils<0, tuple<U...>>(out, t);
}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
long long get_rand(long long r) {
return uniform_int_distribution<long long> (0, r-1)(rng);
}
template<typename T>
vector<T> read_vector(int n) {
vector<T> res(n);
for (int& x : res) cin >> x;
return res;
}
void solve();
int main() {
ios::sync_with_stdio(0); cin.tie(0);
solve();
return 0;
}
#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;
}
// }}}
#line 1 "Math/modint.h"
// ModInt {{{
template<int MD> struct ModInt {
using ll = long long;
int x;
constexpr ModInt() : x(0) {}
constexpr ModInt(ll v) { _set(v % MD + MD); }
constexpr static int mod() { return MD; }
constexpr explicit operator bool() const { return x != 0; }
constexpr ModInt operator + (const ModInt& a) const {
return ModInt()._set((ll) x + a.x);
}
constexpr ModInt operator - (const ModInt& a) const {
return ModInt()._set((ll) x - a.x + MD);
}
constexpr ModInt operator * (const ModInt& a) const {
return ModInt()._set((ll) x * a.x % MD);
}
constexpr ModInt operator / (const ModInt& a) const {
return ModInt()._set((ll) x * a.inv().x % MD);
}
constexpr ModInt operator - () const {
return ModInt()._set(MD - x);
}
constexpr ModInt& operator += (const ModInt& a) { return *this = *this + a; }
constexpr ModInt& operator -= (const ModInt& a) { return *this = *this - a; }
constexpr ModInt& operator *= (const ModInt& a) { return *this = *this * a; }
constexpr ModInt& operator /= (const ModInt& a) { return *this = *this / a; }
friend constexpr ModInt operator + (ll a, const ModInt& b) {
return ModInt()._set(a % MD + b.x);
}
friend constexpr ModInt operator - (ll a, const ModInt& b) {
return ModInt()._set(a % MD - b.x + MD);
}
friend constexpr ModInt operator * (ll a, const ModInt& b) {
return ModInt()._set(a % MD * b.x % MD);
}
friend constexpr ModInt operator / (ll a, const ModInt& b) {
return ModInt()._set(a % MD * b.inv().x % MD);
}
constexpr bool operator == (const ModInt& a) const { return x == a.x; }
constexpr bool operator != (const ModInt& a) const { return x != a.x; }
friend std::istream& operator >> (std::istream& is, ModInt& other) {
ll val; is >> val;
other = ModInt(val);
return is;
}
constexpr friend std::ostream& operator << (std::ostream& os, const ModInt& other) {
return os << other.x;
}
constexpr ModInt pow(ll k) const {
ModInt ans = 1, tmp = x;
while (k) {
if (k & 1) ans *= tmp;
tmp *= tmp;
k >>= 1;
}
return ans;
}
constexpr ModInt inv() const {
if (x < 1000111) {
_precalc(1000111);
return invs[x];
}
int a = x, b = MD, ax = 1, bx = 0;
while (b) {
int q = a/b, t = a%b;
a = b; b = t;
t = ax - bx*q;
ax = bx; bx = t;
}
assert(a == 1);
if (ax < 0) ax += MD;
return ax;
}
static std::vector<ModInt> factorials, inv_factorials, invs;
constexpr static void _precalc(int n) {
if (factorials.empty()) {
factorials = {1};
inv_factorials = {1};
invs = {0};
}
if (n > MD) n = MD;
int old_sz = factorials.size();
if (n <= old_sz) return;
factorials.resize(n);
inv_factorials.resize(n);
invs.resize(n);
for (int i = old_sz; i < n; ++i) factorials[i] = factorials[i-1] * i;
inv_factorials[n-1] = factorials.back().pow(MD - 2);
for (int i = n - 2; i >= old_sz; --i) inv_factorials[i] = inv_factorials[i+1] * (i+1);
for (int i = n-1; i >= old_sz; --i) invs[i] = inv_factorials[i] * factorials[i-1];
}
static int get_primitive_root() {
static int primitive_root = 0;
if (!primitive_root) {
primitive_root = [&]() {
std::set<int> fac;
int v = MD - 1;
for (ll i = 2; i * i <= v; i++)
while (v % i == 0) fac.insert(i), v /= i;
if (v > 1) fac.insert(v);
for (int g = 1; g < MD; g++) {
bool ok = true;
for (auto i : fac)
if (ModInt(g).pow((MD - 1) / i) == 1) {
ok = false;
break;
}
if (ok) return g;
}
return -1;
}();
}
return primitive_root;
}
static ModInt C(int n, int k) {
_precalc(n + 1);
return factorials[n] * inv_factorials[k] * inv_factorials[n-k];
}
private:
// Internal, DO NOT USE.
// val must be in [0, 2*MD)
constexpr inline __attribute__((always_inline)) ModInt& _set(ll v) {
x = v >= MD ? v - MD : v;
return *this;
}
};
template <int MD> std::vector<ModInt<MD>> ModInt<MD>::factorials = {1};
template <int MD> std::vector<ModInt<MD>> ModInt<MD>::inv_factorials = {1};
template <int MD> std::vector<ModInt<MD>> ModInt<MD>::invs = {0};
// }}}
#line 6 "DP/tests/yosupo_cnt_distinct_subseq.test.cpp"
const int MOD = 998244353;
using mint = ModInt<MOD>;
void solve() {
int n; cin >> n;
vector<int> a(n);
REP(i,n) cin >> a[i];
cout << cnt_distinct_subsequences<int, mint> (a) << endl;
}