About Arbitrary Modulo Convolutions

[YOYO-UIAT]

Since ac-library doesn't provide functions for arbitrary modulo convolutions, I wrote an alternative.

Its implementation is poor, but it's enough in most problems.

vector<int> arbitrary_mod_convolution(const vector<int>& v1, const vector<int>& v2, int mod) {
	if (!v1.size() || !v2.size()) return {};
	static constexpr int B = 16, S = (1 << B) - 1;
	vector<int> ans(v1.size() + v2.size() - 1);
	for (int t1 : {0, 1}) for (int t2 : {0, 1}) {
		vector<long long> c1, c2;
		for (int x : v1) c1.push_back(t1 ? x >> B & S : x & S);
		for (int x : v2) c2.push_back(t2 ? x >> B & S : x & S);
		vector<long long> res = atcoder::convolution_ll(c1, c2);
		for (int i = 0; i<int(res.size()); ++i) {
			ans[i] = (ans[i] + res[i] % mod * (t1 ? 1 << B : 1) % mod * (t2 ? 1 << B : 1)) % mod;
		}
	}
	return ans;
}