MikuroXina

/// Searches the maximum value of `query` in section between `lower` (exclusive) and `upper` (exclusive).
fn fibonacci_section(lower: usize, upper: usize, mut query: impl FnMut(usize) -> u32) -> u32 {
    let n = upper - lower - 1;
    if n == 1 {
        return query(1);
    }
    let mut fib = vec![1, 2];
    for i in 2.. {
        let next = fib[i - 2] + fib[i - 1];
        if next > n {

MikuroXina

/// Design reference: https://zenn.dev/yuhi_junior/articles/062cf4f30b083d

use itertools::Itertools;
use std::cell::RefCell;
use std::rc::Rc;

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Cell {
    has_bomb: bool,
    flagged: bool,

MikuroXina

#![feature(float_next_up_down)]

//! Source: http://verifiedby.me/adiary/pub/kashi/image/201406/nas2014.pdf

/// Floating point number with mathematical error.
#[derive(Debug, Clone, Copy, PartialEq, PartialOrd)]
pub struct F64E {
    /// An actual result by the default rounding mode.
    base: f64,
    /// Mathematical error for an ideal result.

MikuroXina

#[derive(Debug, Clone)]
pub struct Crc32 {
    table: [u32; 256],
}

impl Crc32 {
    pub const SOURCE: u32 = 0xedb8_8320;

    pub fn new() -> Self {
        let mut table = [0u32; 256];

MikuroXina

pub fn algorithm_x(
    list: &mut DancingLinkedList,
    stack: &mut Vec<usize>,
    solutions: &mut Vec<Vec<usize>>,
) {
    if list.is_empty() {
        solutions.push(stack.clone());
        return;
    }

MikuroXina

//! The example implementation of full-scratch LR(0) parser, referenced [Wikipedia](https://en.wikipedia.org/wiki/LR_parser).
//!
//! # Rules
//!
//! There are non-terminal terms: Start, Expr and Bool. And there are terminal
//! terms: 0, 1, +. * and $ (end of input).
//!
//! 1. Introduction: `Start :- Expr $`
//! 2. Expr from multiplication: `Expr :- Expr * Bool`
//! 3. Expr from addition: `Expr :- Expr + Bool`

MikuroXina

#[derive(Debug, Clone, PartialEq, Eq, Hash)]
struct TrieNode<const L: usize> {
    children: [Option<Box<TrieNode<L>>>; L],
    // invariant: `words` must not be `0` if `children` is vacant.
    words: usize,
}

impl<const L: usize> TrieNode<L> {
    fn new() -> Self {
        TrieNode {

MikuroXina

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Counter<T: Eq + std::hash::Hash> {
    counts: std::collections::HashMap<T, usize>,
}

impl<T, Q> std::ops::Index<&Q> for Counter<T>
where
    T: Eq + std::hash::Hash + std::borrow::Borrow<Q>,
    Q: Eq + std::hash::Hash + ?Sized,
{

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());
/// }
/// ```