cpp-library

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub shino16/cpp-library

:heavy_check_mark: poset/set_ranked.hpp

Depends on

Verified with

Code

#pragma once

#include "bit/ctz.hpp"
#include "bit/popcnt.hpp"

template <class T, int MaxN = 20>
vector<array<T, MaxN+1>> add_rank(const vector<T>& a) {
  vector<array<T, MaxN+1>> ra(a.size());
  rep(mask, a.size()) ra[mask][popcnt(mask)] = a[mask];
  return ra;
}

template <class T, int MaxN = 20>
vector<T> erase_rank(const vector<array<T, MaxN+1>>& ra) {
  vector<T> a(ra.size());
  rep(mask, a.size()) a[mask] = ra[mask][popcnt(mask)];
  return a;
}

template <class T, int MaxN = 20>
void ranked_zeta(vector<array<T, MaxN + 1>>& v) {
  for (int h = 1; h < v.size(); h <<= 1)
    for (int i = 0; i < v.size(); i += h * 2)
      rep2(j, i, i + h) {
    int jh = j + h;
    rep(d, MaxN + 1) v[jh][d] += v[j][d];
    }
}

template <class T, int MaxN = 20>
void ranked_moebius(vector<array<T, MaxN + 1>>& v) {
  for (int h = 1; h < v.size(); h <<= 1)
    for (int i = 0; i < v.size(); i += h * 2)
      rep2(j, i, i + h) {
    int jh = j + h;
    rep(d, MaxN + 1) v[jh][d] -= v[j][d];
    }
}

// Regards array as a polynomial
// High-degree terms are dropped
template <class T, int MaxN = 20>
void ranked_pointwise_mult(
    vector<array<T, MaxN + 1>>& a, const vector<array<T, MaxN + 1>>& b) {
  rep(mask, a.size()) repr(d, MaxN + 1) {
    T sum = 0;
    rep(i, d + 1) sum += a[mask][i] * b[mask][d - i];
    a[mask][d] = sum;
  }
}

// Regards array as a polynomial
// High-degree terms are dropped
template <class T, int MaxN = 20>
void ranked_pointwise_square(vector<array<T, MaxN + 1>>& a) {
  rep(mask, a.size()) repr(d, MaxN + 1) {
    T sum = 0;
    rep(i, d + 1) sum += a[mask][i] * a[mask][d - i];
    a[mask][d] = sum;
  }
}

template <class T, int MaxN>
vector<T> subset_convolution_square(const vector<T>& a) {
  auto ra = add_rank<T, MaxN>(a);
  ranked_zeta<T, MaxN>(ra);
  ranked_pointwise_square<T, MaxN>(ra);
  ranked_moebius<T, MaxN>(ra);
  return erase_rank<T, MaxN>(ra);
}

template <class T, int MaxN>
vector<T> subset_convolution(const vector<T>& a, const vector<T>& b) {
  if (a == b) return subset_convolution_square<T, MaxN>(a);
  auto ra = add_rank<T, MaxN>(a), rb = add_rank<T, MaxN>(b);
  ranked_zeta<T, MaxN>(ra), ranked_zeta<T, MaxN>(rb);
  ranked_pointwise_mult<T, MaxN>(ra, rb);
  ranked_moebius<T, MaxN>(ra);
  return erase_rank<T, MaxN>(ra);
}

#line 2 "poset/set_ranked.hpp"

#line 2 "prelude.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using vc = vector<char>;
#define rep2(i, m, n) for (auto i = (m); i < (n); i++)
#define rep(i, n) rep2(i, 0, n)
#define repr2(i, m, n) for (auto i = (n); i-- > (m);)
#define repr(i, n) repr2(i, 0, n)
#define all(x) begin(x), end(x)
auto ndvec(int n, auto e) { return vector(n, e); }
auto ndvec(int n, auto ...e) { return vector(n, ndvec(e...)); }
auto comp_key(auto&& f) { return [&](auto&& a, auto&& b) { return f(a) < f(b); }; }
auto& max(const auto& a, const auto& b) { return a < b ? b : a; }
auto& min(const auto& a, const auto& b) { return b < a ? b : a; }
#if __cpp_lib_ranges
namespace R = std::ranges;
namespace V = std::views;
#endif
#line 3 "bit/ctz.hpp"

#pragma GCC target("bmi")

template <class T>
int ctz(T x) {
  if (!x) return sizeof(T) * 8;
  if constexpr (sizeof(T) <= sizeof(unsigned)) {
    return __builtin_ctz((unsigned)x);
  } else if constexpr (sizeof(T) <= sizeof(unsigned long long)) {
    return __builtin_ctzll((unsigned long long)x);
  } else if constexpr (sizeof(T) <= sizeof(unsigned long long) * 2) {
    unsigned long long y = x;
    return y ? ctz(y)
             : sizeof(y) * 8 + ctz((unsigned long long)(x >> sizeof(y) * 8));
  }
}
#line 3 "bit/popcnt.hpp"

#pragma GCC target("popcnt")

template <class T>
int popcnt(T a) {
  if constexpr (sizeof(T) <= sizeof(unsigned)) {
    return __builtin_popcount((unsigned)a);
  } else if constexpr (sizeof(T) <= sizeof(unsigned long long)) {
    return __builtin_popcountll((unsigned long long)a);
  } else if constexpr (sizeof(T) <= sizeof(unsigned long long) * 2) {
    return popcnt((unsigned long long)a) +
           popcnt((unsigned long long)(a >> sizeof(unsigned long long) * 8));
  }
}
#line 5 "poset/set_ranked.hpp"

template <class T, int MaxN = 20>
vector<array<T, MaxN+1>> add_rank(const vector<T>& a) {
  vector<array<T, MaxN+1>> ra(a.size());
  rep(mask, a.size()) ra[mask][popcnt(mask)] = a[mask];
  return ra;
}

template <class T, int MaxN = 20>
vector<T> erase_rank(const vector<array<T, MaxN+1>>& ra) {
  vector<T> a(ra.size());
  rep(mask, a.size()) a[mask] = ra[mask][popcnt(mask)];
  return a;
}

template <class T, int MaxN = 20>
void ranked_zeta(vector<array<T, MaxN + 1>>& v) {
  for (int h = 1; h < v.size(); h <<= 1)
    for (int i = 0; i < v.size(); i += h * 2)
      rep2(j, i, i + h) {
    int jh = j + h;
    rep(d, MaxN + 1) v[jh][d] += v[j][d];
    }
}

template <class T, int MaxN = 20>
void ranked_moebius(vector<array<T, MaxN + 1>>& v) {
  for (int h = 1; h < v.size(); h <<= 1)
    for (int i = 0; i < v.size(); i += h * 2)
      rep2(j, i, i + h) {
    int jh = j + h;
    rep(d, MaxN + 1) v[jh][d] -= v[j][d];
    }
}

// Regards array as a polynomial
// High-degree terms are dropped
template <class T, int MaxN = 20>
void ranked_pointwise_mult(
    vector<array<T, MaxN + 1>>& a, const vector<array<T, MaxN + 1>>& b) {
  rep(mask, a.size()) repr(d, MaxN + 1) {
    T sum = 0;
    rep(i, d + 1) sum += a[mask][i] * b[mask][d - i];
    a[mask][d] = sum;
  }
}

// Regards array as a polynomial
// High-degree terms are dropped
template <class T, int MaxN = 20>
void ranked_pointwise_square(vector<array<T, MaxN + 1>>& a) {
  rep(mask, a.size()) repr(d, MaxN + 1) {
    T sum = 0;
    rep(i, d + 1) sum += a[mask][i] * a[mask][d - i];
    a[mask][d] = sum;
  }
}

template <class T, int MaxN>
vector<T> subset_convolution_square(const vector<T>& a) {
  auto ra = add_rank<T, MaxN>(a);
  ranked_zeta<T, MaxN>(ra);
  ranked_pointwise_square<T, MaxN>(ra);
  ranked_moebius<T, MaxN>(ra);
  return erase_rank<T, MaxN>(ra);
}

template <class T, int MaxN>
vector<T> subset_convolution(const vector<T>& a, const vector<T>& b) {
  if (a == b) return subset_convolution_square<T, MaxN>(a);
  auto ra = add_rank<T, MaxN>(a), rb = add_rank<T, MaxN>(b);
  ranked_zeta<T, MaxN>(ra), ranked_zeta<T, MaxN>(rb);
  ranked_pointwise_mult<T, MaxN>(ra, rb);
  ranked_moebius<T, MaxN>(ra);
  return erase_rank<T, MaxN>(ra);
}
Back to top page