test/FPS/FFT.test.cpp

• View this file on GitHub
• Last update: 2026-07-19 04:18:57+09:00
• Problem: https://judge.yosupo.jp/problem/convolution_mod

Depends on

• FFT (高速フーリエ変換 / 畳み込み) (src/FPS/FFT.hpp)
• Modint (src/modint/modint.hpp)
• test/template.hpp

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/convolution_mod
#include "test/template.hpp"
#include "src/modint/modint.hpp"
#include "src/FPS/FFT.hpp"

int main() {
   cin.tie(0)->sync_with_stdio(0);
   ll N, M;
   cin >> N >> M;
   vector<mm> A(N), B(M);
   for(mm& a : A) cin >> a.x;
   for(mm& b : B) cin >> b.x;

   auto C = conv(move(A), move(B));
   rep(i, 0, sz(C)) cout << C[i].x << " \n"[i + 1 == sz(C)];
}

#line 1 "test/FPS/FFT.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/convolution_mod
#line 1 "test/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = LLONG_MAX / 4;
template<class T> using V = vector<T>;
#define rep(i, a, b) for(ll i = a; i < (b); i++)
#define each(i, a) for(auto&& i : a)
#define all(a) begin(a), end(a)
#define sz(a) ssize(a)
bool chmin(auto& a, auto b) { return a > b ? a = b, 1 : 0; }
bool chmax(auto& a, auto b) { return a < b ? a = b, 1 : 0; }
#line 1 "src/modint/modint.hpp"
const ll mod = 998244353;
struct mm {
   ll x;
   mm(ll x_ = 0) : x(x_ % mod) {
      if(x < 0) x += mod;
   }
   friend mm operator+(mm a, mm b) { return a.x + b.x; }
   friend mm operator-(mm a, mm b) { return a.x - b.x; }
   friend mm operator*(mm a, mm b) { return a.x * b.x; }
   friend mm operator/(mm a, mm b) { return a * b.inv(); }
   // 4 行コピペ  Alt + Shift + クリックで複数カーソル
   friend mm& operator+=(mm& a, mm b) { return a = a.x + b.x; }
   friend mm& operator-=(mm& a, mm b) { return a = a.x - b.x; }
   friend mm& operator*=(mm& a, mm b) { return a = a.x * b.x; }
   friend mm& operator/=(mm& a, mm b) { return a = a * b.inv(); }
   mm inv() const { return pow(mod - 2); }
   mm pow(ll b) const {
      mm a = *this, c = 1;
      while(b) {
         if(b & 1) c *= a;
         a *= a;
         b >>= 1;
      }
      return c;
   }
};
#line 1 "src/FPS/FFT.hpp"
// {998244353, 3}, {1811939329, 13}, {2013265921, 31}
mm g = 3;  // 原始根
void fft(V<mm>& a) {
   ll n = sz(a), lg = __lg(n);
   assert((1 << lg) == n);
   V<mm> b(n);
   rep(l, 1, lg + 1) {
      ll w = n >> l;
      mm s = 1, r = g.pow(mod >> l);
      for(ll u = 0; u < n / 2; u += w) {
         rep(d, 0, w) {
            mm x = a[u << 1 | d], y = a[u << 1 | w | d] * s;
            b[u | d] = x + y;
            b[n >> 1 | u | d] = x - y;
         }
         s *= r;
      }
      swap(a, b);
   }
}
V<mm> conv(V<mm> a, V<mm> b) {
   if(a.empty() || b.empty()) return {};
   size_t s = sz(a) + sz(b) - 1, n = bit_ceil(s);
   // if(min(sz(a), sz(b)) <= 60) 愚直に掛け算
   a.resize(n);
   b.resize(n);
   fft(a);
   fft(b);
   mm inv = mm(n).inv();
   rep(i, 0, n) a[i] *= b[i] * inv;
   reverse(1 + all(a));
   fft(a);
   a.resize(s);
   return a;
}
#line 5 "test/FPS/FFT.test.cpp"

int main() {
   cin.tie(0)->sync_with_stdio(0);
   ll N, M;
   cin >> N >> M;
   vector<mm> A(N), B(M);
   for(mm& a : A) cin >> a.x;
   for(mm& b : B) cin >> b.x;

   auto C = conv(move(A), move(B));
   rep(i, 0, sz(C)) cout << C[i].x << " \n"[i + 1 == sz(C)];
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	all_same_00	AC	250 ms	28 MB
g++	all_same_01	AC	269 ms	28 MB
g++	all_same_02	AC	284 ms	28 MB
g++	all_same_03	AC	267 ms	28 MB
g++	example_00	AC	3 ms	4 MB
g++	example_01	AC	2 ms	4 MB
g++	fft_killer_00	AC	269 ms	28 MB
g++	fft_killer_01	AC	266 ms	28 MB
g++	fft_killer_02	AC	276 ms	28 MB
g++	fft_killer_03	AC	273 ms	28 MB
g++	fft_killer_04	AC	266 ms	28 MB
g++	fft_killer_05	AC	282 ms	28 MB
g++	fft_killer_06	AC	268 ms	28 MB
g++	fft_killer_07	AC	282 ms	28 MB
g++	fft_killer_08	AC	283 ms	28 MB
g++	fft_killer_09	AC	268 ms	28 MB
g++	max_ans_zero_00	AC	273 ms	28 MB
g++	max_random_00	AC	269 ms	28 MB
g++	max_random_01	AC	269 ms	28 MB
g++	medium_00	AC	6 ms	4 MB
g++	medium_01	AC	4 ms	4 MB
g++	medium_02	AC	5 ms	4 MB
g++	medium_all_zero_00	AC	5 ms	4 MB
g++	medium_pre_suf_zero_00	AC	2 ms	4 MB
g++	medium_pre_suf_zero_01	AC	2 ms	4 MB
g++	medium_pre_suf_zero_02	AC	2 ms	4 MB
g++	medium_pre_suf_zero_03	AC	2 ms	4 MB
g++	medium_pre_suf_zero_04	AC	2 ms	4 MB
g++	random_00	AC	243 ms	28 MB
g++	random_01	AC	260 ms	28 MB
g++	random_02	AC	125 ms	16 MB
g++	signed_overflow_00	AC	2 ms	4 MB
g++	small_00	AC	2 ms	4 MB
g++	small_01	AC	2 ms	4 MB
g++	small_02	AC	2 ms	4 MB
g++	small_03	AC	2 ms	4 MB
g++	small_04	AC	2 ms	4 MB
g++	small_05	AC	2 ms	4 MB
g++	small_06	AC	2 ms	4 MB
g++	small_07	AC	2 ms	4 MB
g++	small_08	AC	2 ms	4 MB
g++	small_09	AC	2 ms	4 MB
g++	small_10	AC	2 ms	4 MB
g++	small_11	AC	2 ms	4 MB
g++	small_12	AC	2 ms	4 MB
g++	small_13	AC	2 ms	4 MB
g++	small_14	AC	2 ms	4 MB
g++	small_15	AC	2 ms	4 MB
g++	small_and_large_00	AC	215 ms	28 MB
g++	small_and_large_01	AC	215 ms	28 MB
g++	small_and_large_02	AC	215 ms	28 MB
g++	small_and_large_03	AC	215 ms	28 MB
g++	unsigned_overflow_00	AC	2 ms	4 MB

Back to top page