setfunc/sps_inv.hpp

View this file on GitHub
Last update: 2024-04-04 19:08:10+09:00
Include: #include "setfunc/sps_inv.hpp"
Link: View error logs on GitHub Actions

Depends on

setfunc/ranked_zeta.hpp

Verified with

test/5_atcoder/abc306h.test.cpp

Code

#include "setfunc/ranked_zeta.hpp"

template <typename mint, int LIM>
vc<mint> sps_inv(vc<mint>& dp) {
  const int N = topbit(len(dp));
  assert(len(dp) == (1 << N) && dp[0] == mint(1));
  auto RA = ranked_zeta<mint, LIM>(dp);
  array<mint, LIM + 1> g;
  FOR(s, 1 << N) {
    auto& f = RA[s];
    g[0] = 1;
    FOR(k, 1, N + 1) {
      g[k] = 0;
      FOR(i, k) g[k] -= g[i] * f[k - i];
    }
    RA[s] = g;
  }
  return ranked_mobius<mint, LIM>(RA);
}

#line 2 "setfunc/ranked_zeta.hpp"

template <typename T, int LIM>
vc<array<T, LIM + 1>> ranked_zeta(const vc<T>& f) {
  int n = topbit(len(f));
  assert(n <= LIM);
  assert(len(f) == 1 << n);
  vc<array<T, LIM + 1>> Rf(1 << n);
  for (int s = 0; s < (1 << n); ++s) Rf[s][popcnt(s)] = f[s];
  for (int i = 0; i < n; ++i) {
    int w = 1 << i;
    for (int p = 0; p < (1 << n); p += 2 * w) {
      for (int s = p; s < p + w; ++s) {
        int t = s | 1 << i;
        for (int d = 0; d <= n; ++d) Rf[t][d] += Rf[s][d];
      }
    }
  }
  return Rf;
}

template <typename T, int LIM>
vc<T> ranked_mobius(vc<array<T, LIM + 1>>& Rf) {
  int n = topbit(len(Rf));
  assert(len(Rf) == 1 << n);
  for (int i = 0; i < n; ++i) {
    int w = 1 << i;
    for (int p = 0; p < (1 << n); p += 2 * w) {
      for (int s = p; s < p + w; ++s) {
        int t = s | 1 << i;
        for (int d = 0; d <= n; ++d) Rf[t][d] -= Rf[s][d];
      }
    }
  }
  vc<T> f(1 << n);
  for (int s = 0; s < (1 << n); ++s) f[s] = Rf[s][popcnt(s)];
  return f;
}
#line 2 "setfunc/sps_inv.hpp"

template <typename mint, int LIM>
vc<mint> sps_inv(vc<mint>& dp) {
  const int N = topbit(len(dp));
  assert(len(dp) == (1 << N) && dp[0] == mint(1));
  auto RA = ranked_zeta<mint, LIM>(dp);
  array<mint, LIM + 1> g;
  FOR(s, 1 << N) {
    auto& f = RA[s];
    g[0] = 1;
    FOR(k, 1, N + 1) {
      g[k] = 0;
      FOR(i, k) g[k] -= g[i] * f[k - i];
    }
    RA[s] = g;
  }
  return ranked_mobius<mint, LIM>(RA);
}