Trait cp_library_rs::convolution::ntt::NTTFriendly

pub trait NTTFriendly<Rhs = Self, Output = Self>: Clone + Copy + Add<Rhs, Output = Output> + Sub<Rhs, Output = Output> + Mul<Rhs, Output = Output> + Div<Rhs, Output = Output> + MulAssign<Rhs> + Zero + From<u32> + Fp {
    // Required methods
    fn order() -> u32;
    fn rem() -> u32;
    fn root() -> Self;

    // Provided method
    fn root_pow2m(a: u32) -> Self { ... }
}

FFTに必要な関数

Required Methods

fn order() -> u32

M = 2^k * m + 1 を満たすような k

fn rem() -> u32

M = 2^k * m + 1 を満たすような m

fn root() -> Self

原始根

Provided Methods

fn root_pow2m(a: u32) -> Self

2^m 乗根

Implementors

impl NTTFriendly<Modint<MOD998>, Modint<MOD998>> for M998