convolution/subset_convolution_exp.hpp

• View this file on GitHub
• Last update: 2023-05-04 19:49:25+09:00
• Include: #include "convolution/subset_convolution_exp.hpp"

Depends on

• convolution/subset_convolution.hpp
• convolution/subset_convolution_internal.hpp

Verified with

• convolution/test/exp_of_set_power_series.test.cpp
• convolution/test/subset_convolution_exp_log.test.cpp

Code

#pragma once

#include "subset_convolution.hpp"

template <typename T>
std::vector<T> subset_convolution_exp(const std::vector<T> &a) {
    int n = 0;
    while ((1 << n) < (int)a.size()) {
        ++n;
    }
    assert((int)a.size() == (1 << n));
    assert(a[0] == T(0));
    
    std::vector<T> b;
    b.reserve(1 << n);
    b.push_back(T(1));
    for (int i = 0; i < n; ++i) {
        std::vector<T> c(a.begin() + (1 << i), a.begin() + (2 << i));
        std::vector<T> sc = subset_convolution(b, c);
        for (int j = 0; j < (1 << i); ++j) {
            b.push_back(sc[j]);
        }
    }
    return b;
}

#line 2 "convolution/subset_convolution_exp.hpp"

#line 2 "convolution/subset_convolution.hpp"

#line 2 "convolution/subset_convolution_internal.hpp"

#include <vector>
#include <algorithm>

namespace subset_convolution_internal {

template <typename T>
void add(std::vector<T> &a, const std::vector<T> &b, int to) {
    for (int i = 0; i <= to; ++i) {
        a[i] += b[i];
    }
}

template <typename T>
void sub(std::vector<T> &a, const std::vector<T> &b, int from) {
    for (int i = from; i < (int) a.size(); ++i) {
        a[i] -= b[i];
    }
}

template <typename T>
std::vector<std::vector<T>> setps(int n, const std::vector<T> &a) {
    std::vector<std::vector<T>> sps(1 << n, std::vector<T>(n + 1, T(0)));
    for (int i = 0; i < (1 << n); ++i) {
        sps[i][__builtin_popcount(i)] = a[i];
    }
    return sps;
}

template <typename T>
std::vector<T> rev_setps(int n, const std::vector<std::vector<T>> &sps) {
    std::vector<T> a(1 << n);
    for (int i = 0; i < (1 << n); ++i) {
        a[i] = sps[i][__builtin_popcount(i)];
    }
    return a;
}

} // namespace subset_convolution_internal
#line 4 "convolution/subset_convolution.hpp"

#include <cassert>

template <typename T>
std::vector<T> _subset_conv_mul(const std::vector<T> &a, const std::vector<T> &b, int to) {
    std::vector<T> c(a.size(), T(0));
    for (int i = 0; i <= to; ++i) {
        for (int j = 0; j <= std::min((int) a.size() - i - 1, to); ++j) {
            c[i + j] += a[i] * b[j];
        }
    }
    return c;
}

template <typename T>
std::vector<T> subset_convolution(const std::vector<T> &a, const std::vector<T> &b) {
    int n = 0;
    while ((1 << n) < (int) a.size()) {
        ++n;
    }
    assert((int) a.size() == (1 << n));
    assert((int) b.size() == (1 << n));
    
    std::vector<std::vector<T>> a_ = subset_convolution_internal::setps(n, a);
    std::vector<std::vector<T>> b_ = subset_convolution_internal::setps(n, b);
    for (int d = 0; d < n; ++ d) {
        for (int i = 0; i < (1 << n); ++i) {
            if (i & (1 << d)) {
                subset_convolution_internal::add(a_[i], a_[i ^ (1 << d)], __builtin_popcount(i) - 1);
                subset_convolution_internal::add(b_[i], b_[i ^ (1 << d)], __builtin_popcount(i) - 1);
            }
        }
    }
    for (int i = 0; i < (1 << n); ++i) {
        a_[i] = _subset_conv_mul(a_[i], b_[i], __builtin_popcount(i));
    }
    for (int d = 0; d < n; ++ d) {
        for (int i = 0; i < (1 << n); ++i) {
            if (i & (1 << d)) {
                subset_convolution_internal::sub(a_[i], a_[i ^ (1 << d)], __builtin_popcount(i));
            }
        }
    }
    return subset_convolution_internal::rev_setps(n, a_);
}
#line 4 "convolution/subset_convolution_exp.hpp"

template <typename T>
std::vector<T> subset_convolution_exp(const std::vector<T> &a) {
    int n = 0;
    while ((1 << n) < (int)a.size()) {
        ++n;
    }
    assert((int)a.size() == (1 << n));
    assert(a[0] == T(0));
    
    std::vector<T> b;
    b.reserve(1 << n);
    b.push_back(T(1));
    for (int i = 0; i < n; ++i) {
        std::vector<T> c(a.begin() + (1 << i), a.begin() + (2 << i));
        std::vector<T> sc = subset_convolution(b, c);
        for (int j = 0; j < (1 << i); ++j) {
            b.push_back(sc[j]);
        }
    }
    return b;
}

Back to top page