misc/CountSubseq.h

• View this file on GitHub
• Last update: 2025-11-21 16:12:02+07:00

Depends on

• misc/Compressor.h

Verified with

• tests/Number_of_Subsequences.test.cpp

Code

#include "Compressor.h"

template <class T, class Fp>
Fp CountSubseq(vector<T> a) {
  a = compressor<T>(a);
  vi last(sz(a) + 1, -1);
  vector<Fp> f(sz(a) + 1);
  f[0] = 1;
  for (int i = 0; i < sz(a); ++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/Compressor.h"
template <class T>
vi compressor(vector<T>& v) {
  auto cv = v;
  sort(all(cv));
  cv.erase(unique(all(cv)), cv.end());
  for (auto& e : v) e = lower_bound(all(cv), e) - cv.begin();
  return v;
}
#line 2 "misc/CountSubseq.h"

template <class T, class Fp>
Fp CountSubseq(vector<T> a) {
  a = compressor<T>(a);
  vi last(sz(a) + 1, -1);
  vector<Fp> f(sz(a) + 1);
  f[0] = 1;
  for (int i = 0; i < sz(a); ++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