MikuroXina

/// Finds `x` where `alpha` ** `x` == `beta`.
pub fn discrete_log<const MOD_1: u64, const MOD: u64>(alpha: ModInt<MOD>, beta: ModInt<MOD>) -> Option<u64> {
    assert_eq!(MOD_1 + 1, MOD);
    fn step<const MOD_1: u64, const MOD: u64>(alpha: ModInt<MOD>, beta: ModInt<MOD>, x: &mut ModInt<MOD>, a: &mut ModInt<MOD_1>, b: &mut ModInt<MOD_1>) {
        match x.as_u64() % 3 {
            0 => {
                *x = *x * *x;
                *a = *a * 2.into();
                *b = *b * 2.into();
            }

MikuroXina

/// Group must satisfy:
/// ```rs
/// fn test<G: Group>(m: G, n: G, l: G) {
///     assert_eq!(m.op(&G::id()), m);
///     assert_eq!(G::id().op(&m), m);
///     assert_eq!(m.op(&n.op(&l)), m.op(&n).op(&l));
///     assert_eq!(m.op(&m.inv()), G::id());
///     assert_eq!(m.inv().op(&m), G::id());
/// }
/// ```

MikuroXina

pub fn cum<T: Default + std::ops::AddAssign + Copy>(
    nums: impl IntoIterator<Item = T>,
) -> impl Iterator<Item = T> {
    nums.into_iter().scan(T::default(), |state, item| {
        *state += item;
        Some(*state)
    })
}

pub fn cum2<T: Default + std::ops::AddAssign + Copy, NNS, NS>(nums: NNS) -> Vec<Vec<T>>

MikuroXina

#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct AltSum {
    sum: i64,
    len: usize,
}

impl AltSum {
    pub fn empty() -> Self {
        Self { sum: 0, len: 0 }
    }

MikuroXina

export type Paradoxical<A, R> = (f: Paradoxical<A, R>) => (a: A) => R;

export const Y = <A, R>(f: (g: (a: A) => R) => (a: A) => R): ((a: A) => R) =>
    ((x: Paradoxical<A, R>) => f((lazy) => x(x)(lazy)))(
        (x: Paradoxical<A, R>) => f((lazy) => x(x)(lazy)),
    );

MikuroXina

pub fn inversions(nums: &[usize]) -> Vec<usize> {
    let len = nums.len();
    let mut counts = SegTree::<Sum>::new(len);
    let mut inversions = Vec::with_capacity(len);
    for (i, &num) in nums.into_iter().enumerate() {
        let Sum(inv) = counts.query(0..num);
        inversions.push(i - inv);
        counts.insert(num, Sum(1));
    }
    inversions

MikuroXina

pub fn longest_increasing_subsequence<T: Ord>(nums: impl IntoIterator<Item = T>) -> Vec<usize> {
    let mut nums = nums.into_iter();
    let Some(first) = nums.next() else {
        return vec![];
    };
    let mut len_by_using = vec![1];
    let mut sorted = vec![first];
    for num in nums {
        let lower_bound = sorted.binary_search(&num).unwrap_or_else(|idx| idx);
        if lower_bound == sorted.len() {

MikuroXina

#[inline]
pub fn merge<T, L, R>(left: L, right: R) -> Merge<T, L::IntoIter, R::IntoIter>
where
    T: PartialOrd,
    L: IntoIterator<Item = T>,
    R: IntoIterator<Item = T>,
{
    Merge {
        left: left.into_iter().peekable(),
        right: right.into_iter().peekable(),

MikuroXina

pub fn strongly_connected_components(graph: &[Vec<usize>]) -> Vec<Vec<usize>> {
    let vertexes = graph.len();
    let inv_graph = {
        let mut inv_graph = vec![vec![]; vertexes];
        for (from, adj) in graph.into_iter().enumerate() {
            for &to in adj {
                inv_graph[to].push(from);
            }
        }
        inv_graph

MikuroXina

use std::collections::HashSet;

/// Monoid must satisfy:
/// ```rs
/// fn test<M: Monoid>(m: M, n: M, l: M) {
///   assert_eq!(m.op(M::ID), m);
///   assert_eq!(M::ID.op(m), m);
///   assert_eq!(m.op(n.op(l)), m.op(n).op(l));
/// }
/// ```