math/convolution.hpp

• View this file on GitHub
• Last update: 2025-05-09 07:41:10+00:00
• Include: #include "math/convolution.hpp"

Depends on

• math/NTT.hpp
• math/modint.hpp

Verified with

• verify/yosupo-convolution_mod.test.cpp

Code

#pragma once
#include "NTT"
#include <bits/stdc++.h>
using namespace std;
vector<int> convolution(vector<int>& a, vector<int>& b) {
    int n=1;
    while (n < a.size()+b.size()-1) n <<= 1;
    vector<mint> A(n), B(n);
    for (int i=0; i<a.size(); i++) {
        A[i] = mint(a[i]);
    }
    for (int i=0; i<b.size(); i++) {
        B[i] = mint(b[i]);
    }
    NTT(A, false);
    NTT(B, false);
    for (int i=0; i<n; i++) {
        A[i] *= B[i];
    }
    NTT(A, true);
    vector<int> re(a.size()+b.size()-1);
    for (int i=0; i<a.size()+b.size()-1; i++) {
        re[i] = A[i].val;
    }
    return re;
}

#line 2 "math/modint.hpp"
#include<bits/stdc++.h>
using namespace std;
long long modint_MOD = 998244353;
// mod の値を変更する(デフォルトは998244353)
void setmod(long long x) { modint_MOD = x; }
struct mint {
    long long val;
    mint(long long x=0) {
        val=(x%modint_MOD+modint_MOD)%modint_MOD;
    }
    mint& operator+=(const mint& a) { val = (val + a.val) % modint_MOD; return *this; }
    mint& operator-=(const mint& a) { val = (val - a.val + modint_MOD) % modint_MOD; return *this; }
    mint& operator*=(const mint& a) { val = val * a.val % modint_MOD ; return *this; }
    mint& operator/=(const mint& a) { return *this *= a.inv(); }
    mint operator+(const mint& a) const { return mint(*this) += a; }
    mint operator-(const mint& a) const { return mint(*this) -= a; }
    mint operator*(const mint& a) const { return mint(*this) *= a; }
    mint operator/(const mint& a) const { return mint(*this) /= a; }
    bool operator==(const mint& a) const { return val == a.val; }
    bool operator!=(const mint& a) const { return val != a.val; }
    mint& operator+=(int a) { return *this += mint(a); }
    mint& operator-=(int a) { return *this -= mint(a); }
    mint& operator*=(int a) { return *this *= mint(a); }
    mint& operator/=(int a) { return *this /= mint(a); }
    mint operator+(int a) const { return mint(*this) += a; }
    mint operator-(int a) const { return mint(*this) -= a; }
    mint operator*(int a) const { return mint(*this) *= a; }
    mint operator/(int a) const { return mint(*this) /= a; }
    bool operator==(int a) const { return val == mint(a).val; }
    bool operator!=(int a) const { return val != mint(a).val; }
    friend mint operator+(int a,const mint& b) { return mint(a) + b; }
    friend mint operator-(int a,const mint& b) { return mint(a) - b; }
    friend mint operator*(int a,const mint& b) { return mint(a) * b; }
    friend mint operator/(int a,const mint& b) { return mint(a) / b; }
    friend bool operator==(int a, const mint& b) { return mint(a) == b; }
    friend bool operator!=(int a, const mint& b) { return mint(a) != b; }
    mint& operator++() { return *this += 1; }
    mint operator++(int) { mint r = *this; *this += 1; return r; }
    mint& operator--() { return *this -= 1; }
    mint operator--(int) { mint r = *this; *this -= 1; return r; }
    // modpow を計算する。計算量O(log mod)
    mint pow(long long n) const {
        if (n != 0) n = ((n-2) % (modint_MOD-1) + modint_MOD) % (modint_MOD-1) + 1;
        mint r = 1, a = *this;
        while (n) {
            if (n & 1) r *= a;
            a *= a;
            n >>= 1;
        }
        return r;
    }
    mint inv() const { return pow(-1); }
    friend ostream& operator<<(ostream&s, const mint& a) { return s << a.val; }
    friend istream& operator>>(istream&s, mint& a) { long long x; s >> x; a = mint(x); return s; }
};
vector<mint>fac, ifac;
// n までの階乗を前計算する。O(n)
void buildfac(int n) {
    fac.resize(n + 1);
    ifac.resize(n + 1);
    fac[0] = 1;
    for (int i=1; i<=n; i++) fac[i] = fac[i-1] * i;
    ifac[n] = mint(1) / fac[n];
    for (int i=n; 0<i; i--) ifac[i-1] = ifac[i] * i;
}
// nCk を求める。buildfacの呼び出しが必須。O(1)
mint comb(int n,int k) { return (0 <= k && k <= n ) ? fac[n] * ifac[k] * ifac[n-k] : 0; }
// nPk を求める。buildfacの呼び出しが必須。O(1)
mint perm(int n,int k) { return (0 <= k && k <= n ) ? fac[n] * ifac[n-k] : 0; }
#line 4 "math/NTT.hpp"
using namespace std;
void NTT(vector<mint>& a, bool invert=false) {
    int n = a.size();
    for (int i=1, j=0; i<n; i++) {
        int b;
        for (b=n>>1; j&b; b>>=1) j ^= b;
        j ^= b;
        if (i < j) swap(a[i], a[j]);
    }
    for (int len=2; len<=n; len<<=1) {
        mint wlen = mint(3).pow((998244353 - 1) / len);
        if (invert) wlen = wlen.inv();
        for (int i=0; i<n; i+=len) {
            mint w = 1;
            for (int j=0; j<len/2; j++) {
                mint u = a[i+j], v = a[i+j+len/2] * w;
                a[i+j] = u + v;
                a[i+j+len/2] = u - v;
                w *= wlen;
            }
        }
    }
    if (invert) {
        mint inv_n = mint(n).inv();
        for (auto& x : a) x *= inv_n;
    }
}
#line 4 "math/convolution.hpp"
using namespace std;
vector<int> convolution(vector<int>& a, vector<int>& b) {
    int n=1;
    while (n < a.size()+b.size()-1) n <<= 1;
    vector<mint> A(n), B(n);
    for (int i=0; i<a.size(); i++) {
        A[i] = mint(a[i]);
    }
    for (int i=0; i<b.size(); i++) {
        B[i] = mint(b[i]);
    }
    NTT(A, false);
    NTT(B, false);
    for (int i=0; i<n; i++) {
        A[i] *= B[i];
    }
    NTT(A, true);
    vector<int> re(a.size()+b.size()-1);
    for (int i=0; i<a.size()+b.size()-1; i++) {
        re[i] = A[i].val;
    }
    return re;
}

Back to top page