Function convolution_raw 

pub fn convolution_raw<T, M>(a: &[T], b: &[T]) -> Vec<T>
where
    T: RemEuclidU32 + TryFrom<u32> + Clone,
    T::Error: Debug,
    M: Modulus,

Calculates the $(+, \times)$ convolution in $\mathbb{Z}/p\mathbb{Z}$.

See the module-level documentation for more details.

Returns a empty Vec if a or b is empty.

Constraints

• $2 \leq m \leq 2 \times 10^9$
• $m$ is a prime number.
• $\exists c \text{ s.t. } 2^c \mid (m - 1), |a| + |b| - 1 \leq 2^c$
• $(0, m] \subseteq$ T

where $m$ is M::VALUE.

Complexity

• $O(n \log n + \log m)$ where $n = |a| + |b|$.

Panics

Panics if any element of the result ($\in [0,$ M::VALUE$)$) is outside of the range of T.

Example

use ac_library::{Mod1000000007 as M, Modulus as _};
use proconio::{input, source::once::OnceSource};

const M: i32 = M::VALUE as _;

input! {
    from OnceSource::from(
        "3\n\
         1 2 3\n\
         3\n\
         -1 -2 -3\n",
    ),
    a: [i32],
    b: [i32],
}

assert_eq!(
    ac_library::convolution::convolution_raw::<_, M>(&a, &b),
    [
        (-1i32).rem_euclid(M),
        (-4i32).rem_euclid(M),
        (-10i32).rem_euclid(M),
        (-12i32).rem_euclid(M),
        (-9i32).rem_euclid(M),
    ],
);