test/library_checker/convolution/convolution_mod_2_64.test.cpp

• View this file on GitHub
• Last update: 2024-11-13 13:43:26+09:00
• Problem: https://judge.yosupo.jp/problem/convolution_mod_2_64

Depends on

• Karatsuba Algorithm (lib/convolution/karatsuba_algorithm.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/convolution_mod_2_64"
#include <iostream>
#include <vector>

#include "../../../lib/convolution/karatsuba_algorithm.hpp"

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m; cin >> n >> m;
    vector<unsigned long long> a(n), b(m);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    for(int i = 0; i < m; i++){
        cin >> b[i];
    }
    int k = 1;
    while(k < max(n, m)){
        k *= 2;
    }
    a.resize(k), b.resize(k);
    vector<unsigned long long> c = karatsuba_algorithm(a, b);
    for(int i = 0; i < n + m - 1; i++){
        cout << c[i] << " \n"[i == n + m - 1];
    }
}

#line 1 "test/library_checker/convolution/convolution_mod_2_64.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/convolution_mod_2_64"
#include <iostream>
#include <vector>

#line 2 "lib/convolution/karatsuba_algorithm.hpp"

/**
 * @brief Karatsuba Algorithm
 */

#line 8 "lib/convolution/karatsuba_algorithm.hpp"
#include <cassert>

template <typename T>
std::vector<T> karatsuba_algorithm(std::vector<T> &a, std::vector<T> &b){
    const int n = (int) a.size();
    const int h = n >> 1;
    assert(a.size() == b.size());
    assert((n & (n - 1)) == 0);
    if(n <= 64){
        std::vector<T> res(2 * n - 1);
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < n; ++j){
                res[i + j] += a[i] * b[j];
            }
        }
        return res;
    }
    std::vector<T> p(h), q(h), r(h), s(h), t(h), u(h);
    for(int i = 0; i < h; ++i){
        p[i] = a[i + h];
        q[i] = a[i];
        r[i] = b[i + h];
        s[i] = b[i];
        t[i] = p[i] + q[i];
        u[i] = r[i] + s[i];
    }
    p = karatsuba_algorithm(p, r);
    q = karatsuba_algorithm(q, s);
    t = karatsuba_algorithm(t, u);
    std::vector<T> res(2 * n - 1, 0);
    for(int i = 0; i < n - 1; ++i){
        res[i] += q[i];
        res[i + h] += t[i] - p[i] - q[i];
        res[i + n] += p[i];
    }
    return res;
}
#line 6 "test/library_checker/convolution/convolution_mod_2_64.test.cpp"

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m; cin >> n >> m;
    vector<unsigned long long> a(n), b(m);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    for(int i = 0; i < m; i++){
        cin >> b[i];
    }
    int k = 1;
    while(k < max(n, m)){
        k *= 2;
    }
    a.resize(k), b.resize(k);
    vector<unsigned long long> c = karatsuba_algorithm(a, b);
    for(int i = 0; i < n + m - 1; i++){
        cout << c[i] << " \n"[i == n + m - 1];
    }
}

Back to top page