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;
}
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.