LongMultiplication.cpp

• View this file on GitHub
• Last update: 2023-02-27 10:03:35-03:00
• Link: View error logs on GitHub Actions

Depends on

• bits/stdc++.h

Required by

• LinearRecurrence.cpp
• PolynomialRing.cpp
• PowerSeries.cpp
• polynomial/MultipointEvaluation.cpp

Verified with

• tests/yosupo/find-lr.test.cpp
• tests/yosupo/fps-inv.test.cpp
• tests/yosupo/fps-power.test.cpp
• tests/yosupo/kth-term-lr.test.cpp
• tests/yosupo/multipoint.test.cpp
• tests/yosupo/subset-sum.test.cpp

Code

#ifndef _LIB_LONG_MULTIPLICATION
#define _LIB_LONG_MULTIPLICATION
#include <bits/stdc++.h>

namespace lib {
using namespace std;
namespace math {
struct NaiveMultiplication {
  template<typename T>
  using Transform = void;

  template <typename Field>
  vector<Field> operator()(const vector<Field> &a,
                           const vector<Field> &b) const {
    vector<Field> res(a.size() + b.size());
    for (size_t i = 0; i < a.size(); i++) {
      for (size_t j = 0; j < b.size(); j++) {
        res[i + j] += a[i] * b[j];
      }
    }
    return res;
  }
};

template <typename Mult, typename Field>
vector<Field> shift_conv(const vector<Field> &a, vector<Field> b) {
  if (b.empty())
    return {};
  reverse(b.begin(), b.end());
  int n = a.size();
  int m = b.size();

  auto res = Mult()(a, b);
  return vector<Field>(res.begin() + m - 1, res.end());
}
} // namespace math
} // namespace lib

#endif

#line 1 "LongMultiplication.cpp"


#include <bits/stdc++.h>

namespace lib {
using namespace std;
namespace math {
struct NaiveMultiplication {
  template<typename T>
  using Transform = void;

  template <typename Field>
  vector<Field> operator()(const vector<Field> &a,
                           const vector<Field> &b) const {
    vector<Field> res(a.size() + b.size());
    for (size_t i = 0; i < a.size(); i++) {
      for (size_t j = 0; j < b.size(); j++) {
        res[i + j] += a[i] * b[j];
      }
    }
    return res;
  }
};

template <typename Mult, typename Field>
vector<Field> shift_conv(const vector<Field> &a, vector<Field> b) {
  if (b.empty())
    return {};
  reverse(b.begin(), b.end());
  int n = a.size();
  int m = b.size();

  auto res = Mult()(a, b);
  return vector<Field>(res.begin() + m - 1, res.end());
}
} // namespace math
} // namespace lib

Back to top page