Naive Convolution
(library/convolution/convolution_naive.hpp)

• View this file on GitHub
• Last update: 2023-05-11 13:19:06+09:00
• Include: #include "library/convolution/convolution_naive.hpp"

Naive Convolution

愚直な畳み込みの実装です。列の一方の次数が小さい場合は、こちらを用いる方が高速な場合があります。

Required by

• 任意 $\mathrm{mod}$ 畳み込み (library/convolution/arbitrary_mod_convolution.hpp)
• Convolution $(\mathrm{mod}\ 2 ^ {64})$ (library/convolution/convolution_2_64.hpp)
• Convolution (Large) (library/convolution/convolution_large.hpp)
• Multi Variate Convolution Circular (多変数巡回畳み込み) (library/convolution/multi_variate_convolution_circular.hpp)
• 多倍長整数 (library/math/bigint.hpp)
• Factorial Large (library/math/factorial_large.hpp)
• Unsigned Bigint (library/math/unsigned_bigint.hpp)
• test/src/math/factorial_large/yuki502.cpp

Verified with

• test/src/convolution/arbitrary_mod_convolution/convolution_mod_1000000007.test.cpp
• test/src/convolution/convolution_2_64/convolution_mod_2_64.test.cpp
• test/src/convolution/convolution_2_64/convolution_mod_2_64_6mod.test.cpp
• test/src/convolution/convolution_large/convolution_large.test.cpp
• test/src/convolution/multi_variate_convolution_circular/bitwise_xor_convolution.test.cpp
• test/src/convolution/multi_variate_convolution_circular/dummy.test.cpp
• test/src/convolution/multi_variate_convolution_circular/multivariate_convolution_cyclic.test.cpp
• test/src/math/bigint/NTL_2_A.test.cpp
• test/src/math/bigint/NTL_2_B.test.cpp
• test/src/math/bigint/NTL_2_D.test.cpp
• test/src/math/bigint/NTL_2_E.test.cpp
• test/src/math/bigint/NTL_2_F.test.cpp
• test/src/math/bigint/addition_of_big_integers.test.cpp
• test/src/math/bigint/many_aplusb_128bit.test.cpp
• test/src/math/bigint/multiplication_of_big_integers.test.cpp
• test/src/math/factorial_large/dummy.test.cpp
• test/src/math/factorial_large/factorial.test.cpp
• test/src/math/factorial_large/many_factorials.test.cpp

Code

#ifndef SUISEN_CONVOLUTION_NAIVE
#define SUISEN_CONVOLUTION_NAIVE

#include <vector>

namespace suisen::internal {
    template <typename T, typename R = T>
    std::vector<R> convolution_naive(const std::vector<T>& a, const std::vector<T>& b) {
        const int n = a.size(), m = b.size();
        std::vector<R> c(n + m - 1);
        if (n < m) {
            for (int j = 0; j < m; j++) for (int i = 0; i < n; i++) c[i + j] += R(a[i]) * b[j];
        } else {
            for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) c[i + j] += R(a[i]) * b[j];
        }
        return c;
    }
} // namespace suisen


#endif // SUISEN_CONVOLUTION_NAIVE

#line 1 "library/convolution/convolution_naive.hpp"



#include <vector>

namespace suisen::internal {
    template <typename T, typename R = T>
    std::vector<R> convolution_naive(const std::vector<T>& a, const std::vector<T>& b) {
        const int n = a.size(), m = b.size();
        std::vector<R> c(n + m - 1);
        if (n < m) {
            for (int j = 0; j < m; j++) for (int i = 0; i < n; i++) c[i + j] += R(a[i]) * b[j];
        } else {
            for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) c[i + j] += R(a[i]) * b[j];
        }
        return c;
    }
} // namespace suisen

Back to top page