1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

//! modを取る作用付きモノイド

use crate::{
    algebraic_structure::{
        affine1d::{Affine, AffineTransform},
        extmonoid::ExtMonoid,
    },
    number_theory::modint::*,
    utils::num_traits::Zero,
};

/// ## 1次元Affine変換
/// - 区間を $`ax + b`$ で更新（Affine変換）
/// - 区間和を取得
#[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)
    }
}

/// ## 一次関数のupdate + 関数合成
/// - 区間を $`ax + b`$ で更新
/// - 区間を関数として合成
#[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)
    }
}