verify/yosupo/yosupo-convolution_mod_1000000007-karatsuba.test.cpp

• View this file on GitHub
• Last update: 2022-07-21 16:12:33-04:00
• Problem: https://judge.yosupo.jp/problem/convolution_mod_1000000007

Depends on

• library/contest/template-minimal.hpp
• library/modular-arithmetic/mod-int2.hpp
• library/polynomial/karatsuba.hpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/convolution_mod_1000000007"

#include "../../library/contest/template-minimal.hpp"
#include "../../library/polynomial/karatsuba.hpp"
#include "../../library/modular-arithmetic/mod-int2.hpp"

int main() {
	const int MOD = 1e9 + 7;
	using mi = Mint<MOD, 5>;
	using namespace Karatsuba;
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int sa, sb;
	cin >> sa >> sb;
	vector<mi> a(sa);
	for (int i = 0; i < sa; i++)
		cin >> a[i];
	vector<mi> b(sb);
	for (int i = 0; i < sb; i++)
		cin >> b[i];
	vector<mi> c = convolution<mi>(a, b);
	for (int i = 0; i < (int)c.size(); i++)
		cout << c[i] << " ";
	cout << '\n';
	return 0;
}

#define PROBLEM "https://judge.yosupo.jp/problem/convolution_mod_1000000007"


#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <iostream>
#include <iomanip>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

namespace Karatsuba {

int size(int s) {
	return s > 1 ? 32 - __builtin_clz(s - 1) : 0;
}

template <class T> void karatsuba(T* a, T* b, T* c, T* t, int n) {
	int ca = 0, cb = 0;
	for (int i = 0; i < n; i++)
		ca += (a[i] != 0), cb += (b[i] != 0);
	if (std::min(ca, cb) <= 1500 / n) { // not many multiplications

		if (ca > cb) 
			std::swap(ca, cb);
		for (int i = 0; i < n; i++) 
			if (a[i] != 0)
				for (int j = 0; j < n; j++)
					c[i + j] += a[i] * b[j];

	} else {
		int h = n >> 1;
		karatsuba(a, b, c, t, h); // a0 * b0

		karatsuba(a + h, b + h, c + n, t, h); // a1 * b1

		for (int i = 0; i < h; i++)
			a[i] += a[i + h], b[i] += b[i + h];
		karatsuba(a, b, t, t + n, h); // (a0 + a1) * (b0 + b1)

		for (int i = 0; i < h; i++)
			a[i] -= a[i + h], b[i] -= b[i + h];
		for (int i = 0; i < n; i++)
			t[i] -= c[i] + c[i + n];
		for (int i = 0; i < n; i++)
			c[i + h] += t[i], t[i] = 0;
	}
}

template <class T> std::vector<T> convolution(std::vector<T> a, std::vector<T> b) {
	int sa = (int)a.size(), sb = (int)b.size();
	if (!sa || !sb) 
		return {};
	int n = (1 << size(std::max(sa, sb)));
	a.resize(n);
	b.resize(n);
	std::vector<T> c(2 * n), t(2 * n);
	karatsuba(&a[0], &b[0], &c[0], &t[0], n);
	c.resize(sa + sb - 1);
	return c;
}

}

// 5 is a root of both mods

template <int MOD, int RT> struct Mint {
	static const int mod = MOD;
	static constexpr Mint rt() { return RT; } // primitive root for FFT

	static constexpr int md() { return MOD; } // primitive root for FFT

	int v; 
	explicit operator int() const { return v; } // explicit -> don't silently convert to int

	explicit operator bool() const { return v != 0; }
	Mint() { v = 0; }
	Mint(long long _v) { v = int((-MOD <= _v && _v < MOD) ? _v : _v % MOD); if (v < 0) v += MOD; }
	friend bool operator==(const Mint& a, const Mint& b) { return a.v == b.v; }
	friend bool operator!=(const Mint& a, const Mint& b) { return !(a == b); }
	friend bool operator<(const Mint& a, const Mint& b) { return a.v < b.v; }
	friend bool operator>(const Mint& a, const Mint& b) { return a.v > b.v; }
	friend bool operator<=(const Mint& a, const Mint& b) { return a.v <= b.v; }
	friend bool operator>=(const Mint& a, const Mint& b) { return a.v >= b.v; }
	friend std::istream& operator >> (std::istream& in, Mint& a) { 
		long long x; std::cin >> x; a = Mint(x); return in; }
	friend std::ostream& operator << (std::ostream& os, const Mint& a) { return os << a.v; }
	Mint& operator+=(const Mint& m) { 
		if ((v += m.v) >= MOD) v -= MOD; 
		return *this; }
	Mint& operator-=(const Mint& m) { 
		if ((v -= m.v) < 0) v += MOD; 
		return *this; }
	Mint& operator*=(const Mint& m) { 
		v = (long long)v * m.v % MOD; return *this; }
	Mint& operator/=(const Mint& m) { return (*this) *= inv(m); }
	friend Mint pow(Mint a, long long p) {
		Mint ans = 1; assert(p >= 0);
		for (; p; p /= 2, a *= a) if (p & 1) ans *= a;
		return ans; 
	}
	friend Mint inv(const Mint& a) { assert(a.v != 0); return pow(a, MOD - 2); }
	Mint operator-() const { return Mint(-v); }
	Mint& operator++() { return *this += 1; }
	Mint& operator--() { return *this -= 1; }
	friend Mint operator+(Mint a, const Mint& b) { return a += b; }
	friend Mint operator-(Mint a, const Mint& b) { return a -= b; }
	friend Mint operator*(Mint a, const Mint& b) { return a *= b; }
	friend Mint operator/(Mint a, const Mint& b) { return a /= b; }
};

int main() {
	const int MOD = 1e9 + 7;
	using mi = Mint<MOD, 5>;
	using namespace Karatsuba;
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int sa, sb;
	cin >> sa >> sb;
	vector<mi> a(sa);
	for (int i = 0; i < sa; i++)
		cin >> a[i];
	vector<mi> b(sb);
	for (int i = 0; i < sb; i++)
		cin >> b[i];
	vector<mi> c = convolution<mi>(a, b);
	for (int i = 0; i < (int)c.size(); i++)
		cout << c[i] << " ";
	cout << '\n';
	return 0;
}

Back to top page