fps/bbb.hpp

• View this file on GitHub
• Last update: 2025-04-05 12:46:42+09:00
• Include: #include "fps/bbb.hpp"

Depends on

• fps/poly_multi_eval.hpp

Verified with

• verify/yuki/yuki_1510.test.cpp

Code

#ifndef KK2_FPS_BBB_HPP
#define KK2_FPS_BBB_HPP 1

#include <utility>
#include <vector>

#include "poly_multi_eval.hpp"

namespace kk2 {

// f(X) / \prod (X - a_i) = \sum c_i / (X - a_i)
// return {c_i}
template <class FPS, class mint = typename FPS::value_type>
std::vector<mint> BBB(const std::vector<mint> &a, const FPS &f) {
    if (a.empty() || f.empty()) return std::vector<mint>(a.size(), mint());
    int n = (int)a.size();
    SubProductTree<FPS> mpe(a);
    FPS gp = mpe.pr[1].diff();
    std::vector<mint> gpv = mpe.query(gp);
    std::vector<mint> fv = mpe.query(f);
    std::vector<mint> ret(n);
    for (int i = 0; i < n; i++) ret[i] = fv[i] / gpv[i];
    return ret;
}

// f(X) / \prod (1 - a_i X) = \sum c_i / (1- a_i X)
// return {c_i}
template <class FPS, class mint = typename FPS::value_type>
std::vector<mint> BBB1(const std::vector<mint> &a, const FPS &f) {
    if (a.empty() || f.empty()) return std::vector<mint>(a.size(), mint(0));
    int n = (int)a.size();
    std::vector<mint> ima(a.size());
    mint prod = 1;
    for (int i = 0; i < (int)a.size(); i++) {
        ima[i] = a[i].inv();
        prod *= -ima[i];
    }
    std::vector<mint> ret = BBB(ima, f);
    for (int i = 0; i < n; i++) ret[i] *= -a[i] * prod;
    return ret;
}

// f(X) / \prod (X - a_i)^d_i =  \sum c_i,j / (X - a_i)^j
// return {c_i,j}
template <class FPS, class mint = typename FPS::value_type> std::vector<std::vector<mint>>
BBB(const std::vector<mint> &a, const std::vector<mint> &d, const FPS &f) {
    // hoge
}

} // namespace kk2

#endif // KK2_FPS_BBB_HPP

#line 1 "fps/bbb.hpp"



#include <utility>
#include <vector>

#line 1 "fps/poly_multi_eval.hpp"



#include <functional>
#line 6 "fps/poly_multi_eval.hpp"

namespace kk2 {

template <class FPS, class mint = typename FPS::value_type> struct SubProductTree {
    int _n, size;
    std::vector<int> l, r;
    std::vector<FPS> pr;
    std::vector<mint> v;
    FPS f;

    SubProductTree(const std::vector<mint> &v_) : _n(int(v_.size())), v(v_) {
        size = 1;
        while (size < _n) size <<= 1;
        pr.resize(size << 1);
        l.resize(size << 1, _n);
        r.resize(size << 1, _n);
        build();
    }

    SubProductTree(const std::vector<mint> &v_, const FPS &f_) : SubProductTree(v_) {
        this->f = f_;
    }

    void set(const FPS &f_) { this->f = f_; }

    void build() {
        for (int i = 0; i < _n; i++) {
            l[i + size] = i;
            r[i + size] = i + 1;
            pr[i + size] = {-v[i], 1};
        }
        for (int i = size - 1; i > 0; i--) {
            l[i] = l[i << 1 | 0];
            r[i] = r[i << 1 | 1];
            if (pr[i << 1 | 0].empty()) continue;
            else if (pr[i << 1 | 1].empty()) pr[i] = pr[i << 1 | 0];
            else pr[i] = pr[i << 1 | 0] * pr[i << 1 | 1];
        }
    }

    std::vector<mint> query(const FPS &f) {
        this->f = f;
        return query();
    }

    std::vector<mint> query() {
        if (f.empty() || !_n) return FPS(_n, mint(0));
        std::vector<mint> ret;
        ret.reserve(_n);
        auto rec = [&](auto self, FPS a, int idx) -> void {
            if (l[idx] == r[idx]) return;
            a %= pr[idx];
            if (a.size() <= 64u) {
                for (int i = l[idx]; i < r[idx]; i++) { ret.push_back(a.eval(v[i])); }
                return;
            }
            self(self, a, idx << 1 | 0);
            self(self, a, idx << 1 | 1);
        };
        rec(rec, f, 1);
        return ret;
    }
};

template <class FPS, class mint = typename FPS::value_type>
std::vector<mint> MultiEval(const std::vector<mint> &v, const FPS &f) {
    SubProductTree<FPS> mpe(v, f);
    return mpe.query();
}

} // namespace kk2


#line 8 "fps/bbb.hpp"

namespace kk2 {

// f(X) / \prod (X - a_i) = \sum c_i / (X - a_i)
// return {c_i}
template <class FPS, class mint = typename FPS::value_type>
std::vector<mint> BBB(const std::vector<mint> &a, const FPS &f) {
    if (a.empty() || f.empty()) return std::vector<mint>(a.size(), mint());
    int n = (int)a.size();
    SubProductTree<FPS> mpe(a);
    FPS gp = mpe.pr[1].diff();
    std::vector<mint> gpv = mpe.query(gp);
    std::vector<mint> fv = mpe.query(f);
    std::vector<mint> ret(n);
    for (int i = 0; i < n; i++) ret[i] = fv[i] / gpv[i];
    return ret;
}

// f(X) / \prod (1 - a_i X) = \sum c_i / (1- a_i X)
// return {c_i}
template <class FPS, class mint = typename FPS::value_type>
std::vector<mint> BBB1(const std::vector<mint> &a, const FPS &f) {
    if (a.empty() || f.empty()) return std::vector<mint>(a.size(), mint(0));
    int n = (int)a.size();
    std::vector<mint> ima(a.size());
    mint prod = 1;
    for (int i = 0; i < (int)a.size(); i++) {
        ima[i] = a[i].inv();
        prod *= -ima[i];
    }
    std::vector<mint> ret = BBB(ima, f);
    for (int i = 0; i < n; i++) ret[i] *= -a[i] * prod;
    return ret;
}

// f(X) / \prod (X - a_i)^d_i =  \sum c_i,j / (X - a_i)^j
// return {c_i,j}
template <class FPS, class mint = typename FPS::value_type> std::vector<std::vector<mint>>
BBB(const std::vector<mint> &a, const std::vector<mint> &d, const FPS &f) {
    // hoge
}

} // namespace kk2

Back to top page