Skip to main content

library_checker/convolution/
gcd_convolution.rs

1use competitive::prelude::*;
2use competitive::{
3    algebra::AddMulOperation,
4    math::{ConvolveSteps, GcdConvolve},
5    num::montgomery::MInt998244353 as M,
6};
7
8#[verify::library_checker("gcd_convolution")]
9pub fn gcd_convolution(reader: impl Read, writer: impl Write) {
10    prepare_io!(reader, writer);
11    sc!(n, mut a: [M; n], mut b: [M; n]);
12    a.insert(0, Default::default());
13    b.insert(0, Default::default());
14    let c = GcdConvolve::<AddMulOperation<_>>::convolve(a, b);
15    pp!(@it &c[1..]);
16}