use crate::{
algebraic_structure::{
affine1d::{Affine, AffineTransform},
extmonoid::ExtMonoid,
},
number_theory::modint::*,
utils::num_traits::Zero,
};
#[derive(Debug)]
pub struct AffineSum<const MOD: u32>;
impl<const MOD: u32> ExtMonoid for AffineSum<MOD> {
type X = Modint<MOD>;
type F = Affine<Modint<MOD>>;
fn id_x() -> Self::X {
Self::X::zero()
}
fn id_f() -> Self::F {
Self::F::id_()
}
fn op(x: &Self::X, y: &Self::X) -> Self::X {
*x + *y
}
fn composition(x: &Self::F, y: &Self::F) -> Self::F {
y.compose(x)
}
fn mapping(x: &Self::X, y: &Self::F) -> Self::X {
y.apply(*x)
}
fn aggregate(x: &Self::F, p: usize) -> Self::F {
let &(a, b) = x;
(a, b * p)
}
}
#[derive(Debug)]
pub struct AffineUpdateComposite<const MOD: u32>;
impl<const MOD: u32> ExtMonoid for AffineUpdateComposite<MOD> {
type X = Affine<Modint<MOD>>;
type F = Affine<Modint<MOD>>;
fn id_x() -> Self::X {
Self::X::id_()
}
fn id_f() -> Self::F {
Self::F::id_()
}
fn op(x: &Self::X, y: &Self::X) -> Self::X {
y.compose(x)
}
fn composition(_x: &Self::F, y: &Self::F) -> Self::F {
*y
}
fn mapping(_x: &Self::X, y: &Self::F) -> Self::X {
*y
}
fn aggregate(x: &Self::F, p: usize) -> Self::F {
x.pow(p)
}
}