test/FPS/FFT_fast.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

• 32 bit で加減算をちゃんと書いた Modint (src/extra/modint_fast.hpp)
• FFT (bit reversal ver.) (src/FPS/FFT_fast.hpp)
• test/template.hpp

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/convolution_mod
#include "test/template.hpp"
#include "src/extra/modint_fast.hpp"
#include "src/FPS/FFT_fast.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_fast.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/extra/modint_fast.hpp"
const uint32_t mod = 998244353;
struct mm {
   uint32_t x;
   mm() : x(0) {}
   template<class T> mm(T x_) : x(x_ % mod) {
      if(x >= mod) x += mod;
   }
   friend mm operator+(mm a, mm b) {
      a.x += b.x;
      if(a.x >= mod) a.x -= mod;
      return a;
   }
   friend mm operator-(mm a, mm b) {
      a.x -= b.x;
      if(a.x >= mod) a.x += mod;
      return a;
   }
   friend mm operator*(mm a, mm b) { return (uint64_t)a.x * b.x; }
   friend mm operator/(mm a, mm b) { return a * b.inv(); }
   friend mm& operator+=(mm& a, mm b) { return a = a + b; }
   friend mm& operator-=(mm& a, mm b) { return a = a - b; }
   friend mm& operator*=(mm& a, mm b) { return a = a * b; }
   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_fast.hpp"
// modint を u32 にして加減算を真面目にやると速い
mm g = 3;  // 原始根
void fft(V<mm>& a) {
   ll n = sz(a), lg = __lg(n);
   static auto z = [] {
      V<mm> z(30);
      mm s = 1;
      rep(i, 2, 32) {
         z[i - 2] = s * g.pow(mod >> i);
         s *= g.inv().pow(mod >> i);
      }
      return z;
   }();
   rep(l, 0, lg) {
      ll w = 1 << (lg - l - 1);
      mm s = 1;
      rep(k, 0, 1 << l) {
         ll o = k << (lg - l);
         rep(i, o, o + w) {
            mm x = a[i], y = a[i + w] * s;
            a[i] = x + y;
            a[i + w] = x - y;
         }
         s *= z[countr_zero<uint64_t>(~k)];
      }
   }
}
// コピペ
void ifft(V<mm>& a) {
   ll n = sz(a), lg = __lg(n);
   static auto z = [] {
      V<mm> z(30);
      mm s = 1;
      rep(i, 2, 32) {  // g を逆数に
         z[i - 2] = s * g.inv().pow(mod >> i);
         s *= g.pow(mod >> i);
      }
      return z;
   }();
   for(ll l = lg; l--;) {  // 逆順に
      ll w = 1 << (lg - l - 1);
      mm s = 1;
      rep(k, 0, 1 << l) {
         ll o = k << (lg - l);
         rep(i, o, o + w) {
            mm x = a[i], y = a[i + w];  // *s を下に移動
            a[i] = x + y;
            a[i + w] = (x - y) * s;
         }
         s *= z[countr_zero<uint64_t>(~k)];
      }
   }
}
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;
   ifft(a);
   a.resize(s);
   return a;
}
#line 5 "test/FPS/FFT_fast.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	156 ms	14 MB
g++	all_same_01	AC	176 ms	14 MB
g++	all_same_02	AC	176 ms	14 MB
g++	all_same_03	AC	176 ms	14 MB
g++	example_00	AC	2 ms	4 MB
g++	example_01	AC	2 ms	4 MB
g++	fft_killer_00	AC	179 ms	14 MB
g++	fft_killer_01	AC	178 ms	14 MB
g++	fft_killer_02	AC	175 ms	14 MB
g++	fft_killer_03	AC	182 ms	14 MB
g++	fft_killer_04	AC	188 ms	14 MB
g++	fft_killer_05	AC	182 ms	14 MB
g++	fft_killer_06	AC	176 ms	14 MB
g++	fft_killer_07	AC	191 ms	14 MB
g++	fft_killer_08	AC	192 ms	14 MB
g++	fft_killer_09	AC	182 ms	14 MB
g++	max_ans_zero_00	AC	176 ms	14 MB
g++	max_random_00	AC	195 ms	14 MB
g++	max_random_01	AC	183 ms	14 MB
g++	medium_00	AC	4 ms	4 MB
g++	medium_01	AC	3 ms	4 MB
g++	medium_02	AC	4 ms	4 MB
g++	medium_all_zero_00	AC	4 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	153 ms	13 MB
g++	random_01	AC	161 ms	13 MB
g++	random_02	AC	86 ms	9 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	3 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	124 ms	14 MB
g++	small_and_large_01	AC	127 ms	14 MB
g++	small_and_large_02	AC	133 ms	11 MB
g++	small_and_large_03	AC	126 ms	11 MB
g++	unsigned_overflow_00	AC	2 ms	4 MB

Back to top page