library/setpowerseries/Base.hpp

View this file on GitHub
Last update: 2025-11-24 18:49:07+09:00
Include: #include "library/setpowerseries/Base.hpp"

Depends on

Required by

library/setpowerseries/Compose.hpp

Verified with

test/library-checker/SPS/ExpOfSetPowerSeries.test.cpp

Code

#pragma once
#include "library/bitwise/Ranked.hpp"
#include "library/util/Valarray.hpp"

template <typename T> struct SetPowerSeries : Valarray<T> {
    using SPS = SetPowerSeries;
    using Valarray<T>::Valarray;
    using Valarray<T>::size;
    using Valarray<T>::at;
    using value_type = T;

    SetPowerSeries(const std::vector<T> &f) : Valarray<T>(f) {}

    SPS operator-() const { return SPS(Valarray<T>::operator-()); }
    SPS operator*(const SPS &b) const {
        return SPS(BitwiseRanked::convolution<T>(*this, b));
    }
    SPS &operator*=(const SPS &b) { return (*this) = (*this) * b; }
};

#line 2 "library/bitwise/Util.hpp"
namespace bitwise{
  static int log2(int N){
    int n=__builtin_ffs(N)-1;
    assert((1<<n)==N);
    return n;
  }
  static bool in(int S,int a){ return (S>>a)&1; }
}
#line 3 "library/bitwise/Ranked.hpp"
#define REP_(i, n) for (int i = 0; i < (n); i++)
#define RREP_(i, n) for (int i = (n) - 1; i >= 0; i--)
class BitwiseRanked {
    static int popcount(int S) { return __builtin_popcount(S); }

  public:
    template <typename T>
    static std::vector<std::vector<T>> zeta(const std::vector<T> &A) {
        const int n = bitwise::log2(A.size());
        std::vector<std::vector<T>> RA(1 << n, std::vector<T>(n + 1, 0));
        REP_(S, 1 << n) RA[S][popcount(S)] = A[S];
        REP_(i, n)
        REP_(S, 1 << n)
        if (!bitwise::in(S, i))
            REP_(d, n + 1) RA[S | (1 << i)][d] += RA[S][d];
        return RA;
    }
    template <typename T>
    static std::vector<T> mobius(std::vector<std::vector<T>> RA) {
        const int n = bitwise::log2(RA.size());
        REP_(i, n)
        REP_(S, 1 << n)
        if (!bitwise::in(S, i))
            REP_(d, n + 1) RA[S | (1 << i)][d] -= RA[S][d];
        std::vector<T> A(1 << n);
        REP_(S, 1 << n) A[S] = RA[S][popcount(S)];
        return A;
    }
    template <typename T>
    static std::vector<T> convolution(const std::vector<T> &A,
                                      const std::vector<T> &B) {
        const int n = bitwise::log2(A.size());
        auto RA = zeta(A);
        auto RB = zeta(B);
        REP_(S, 1 << n) {
            auto &ra = RA[S], rb = RB[S];
            RREP_(d, n + 1) {
                ra[d] *= rb[0];
                REP_(i, d) ra[d] += ra[i] * rb[d - i];
            }
        }
        return mobius(RA);
    }
};
#undef REP_
#undef RREP_
#line 1 "library/util/Valarray.hpp"
#include <functional>
#include <ranges>
#include <vector>

template <typename T> struct Valarray : std::vector<T> {
    using std::vector<T>::vector; // コンストラクタ継承
    Valarray(const std::vector<T> &v) : std::vector<T>(v.begin(), v.end()) {}

  private:
    template <typename Op>
    Valarray &apply_inplace(const Valarray &other, Op op) {
        if (this->size() < other.size())
            this->resize(other.size(), T(0));

        for (auto [a, b] : std::views::zip(*this, other))
            a = op(a, b);

        return *this;
    }

  public:
    Valarray &operator+=(const Valarray &other) {
        return apply_inplace(other, std::plus<>());
    }
    Valarray &operator-=(const Valarray &other) {
        return apply_inplace(other, std::minus<>());
    }
    Valarray &operator*=(const Valarray &other) {
        return apply_inplace(other, std::multiplies<>());
    }
    Valarray &operator/=(const Valarray &other) {
        return apply_inplace(other, std::divides<>());
    }

    friend Valarray operator+(Valarray a, const Valarray &b) { return a += b; }
    friend Valarray operator-(Valarray a, const Valarray &b) { return a -= b; }
    friend Valarray operator*(Valarray a, const Valarray &b) { return a *= b; }
    friend Valarray operator/(Valarray a, const Valarray &b) { return a /= b; }

    Valarray operator-() const {
        Valarray g = *this;
        for (T &a : g)
            a = -a;
        return g;
    }
};
#line 4 "library/setpowerseries/Base.hpp"

template <typename T> struct SetPowerSeries : Valarray<T> {
    using SPS = SetPowerSeries;
    using Valarray<T>::Valarray;
    using Valarray<T>::size;
    using Valarray<T>::at;
    using value_type = T;

    SetPowerSeries(const std::vector<T> &f) : Valarray<T>(f) {}

    SPS operator-() const { return SPS(Valarray<T>::operator-()); }
    SPS operator*(const SPS &b) const {
        return SPS(BitwiseRanked::convolution<T>(*this, b));
    }
    SPS &operator*=(const SPS &b) { return (*this) = (*this) * b; }
};