$[x^i]c = \sum_{j} [x^{i+j}]a [x^j]b$
(fps/middle_product.hpp)

• View this file on GitHub
• Last update: 2024-01-05 02:16:31+09:00
• Include: #include "fps/middle_product.hpp"

説明

$N$ 次多項式 $a$ と $M$ 時多項式 $b$ について $[x^i]c = \sum_{j} [x^{i+j}]a [x^j]b$ となる $N-M$ 次多項式 $c$ を求める。 $O(N\log N)$

Depends on

• modint/base.hpp

Verified with

• test/yuki/yuki_1796.test.cpp

Code

#pragma once

#include <algorithm>
#include <bit>
#include <cassert>
#include <ranges>
#include <vector>

#include "../modint/base.hpp"

namespace ebi {

template <Modint mint,
          std::vector<mint> (*convolution)(const std::vector<mint> &,
                                           const std::vector<mint> &)>
std::vector<mint> middle_product(const std::vector<mint> &a,
                                 const std::vector<mint> &b) {
    assert(a.size() >= b.size());
    if (std::min(a.size() - b.size() + 1, b.size()) <= 60) {
        return middle_product_naive<mint>(a, b);
    }
    auto rb = b;
    std::reverse(rb.begin(), rb.end());
    std::vector<mint> c = convolution(a, rb);
    c.resize(a.size());
    c.erase(c.begin(), c.begin() + b.size() - 1);
    return c;
}

template <Modint mint>
std::vector<mint> middle_product_naive(const std::vector<mint> &a,
                                       const std::vector<mint> &b) {
    int n = (int)a.size();
    int m = (int)b.size();
    assert(n >= m);
    std::vector<mint> c(n - m + 1, 0);
    for (int i : std::views::iota(0, n - m + 1)) {
        for (int j : std::views::iota(0, m)) {
            c[i] += b[j] * a[i + j];
        }
    }
    return c;
}

}  // namespace ebi

#line 2 "fps/middle_product.hpp"

#include <algorithm>
#include <bit>
#include <cassert>
#include <ranges>
#include <vector>

#line 2 "modint/base.hpp"

#include <concepts>
#include <iostream>
#include <utility>

namespace ebi {

template <class T>
concept Modint = requires(T a, T b) {
    a + b;
    a - b;
    a * b;
    a / b;
    a.inv();
    a.val();
    a.pow(std::declval<long long>());
    T::mod();
};

template <Modint mint> std::istream &operator>>(std::istream &os, mint &a) {
    long long x;
    os >> x;
    a = x;
    return os;
}

template <Modint mint>
std::ostream &operator<<(std::ostream &os, const mint &a) {
    return os << a.val();
}

}  // namespace ebi
#line 10 "fps/middle_product.hpp"

namespace ebi {

template <Modint mint,
          std::vector<mint> (*convolution)(const std::vector<mint> &,
                                           const std::vector<mint> &)>
std::vector<mint> middle_product(const std::vector<mint> &a,
                                 const std::vector<mint> &b) {
    assert(a.size() >= b.size());
    if (std::min(a.size() - b.size() + 1, b.size()) <= 60) {
        return middle_product_naive<mint>(a, b);
    }
    auto rb = b;
    std::reverse(rb.begin(), rb.end());
    std::vector<mint> c = convolution(a, rb);
    c.resize(a.size());
    c.erase(c.begin(), c.begin() + b.size() - 1);
    return c;
}

template <Modint mint>
std::vector<mint> middle_product_naive(const std::vector<mint> &a,
                                       const std::vector<mint> &b) {
    int n = (int)a.size();
    int m = (int)b.size();
    assert(n >= m);
    std::vector<mint> c(n - m + 1, 0);
    for (int i : std::views::iota(0, n - m + 1)) {
        for (int j : std::views::iota(0, m)) {
            c[i] += b[j] * a[i + j];
        }
    }
    return c;
}

}  // namespace ebi

Back to top page