// codesnip-guard: TableOperation
#[cfg_attr(any(),rustfmt::skip)]pub use self::table_operation_impl::{OperationTable,TableOperation};#[cfg_attr(any(),rustfmt::skip)]mod table_operation_impl{use super::{AssociatedValue,Associative,Invertible,Magma,Unital};use std::marker::PhantomData;#[doc=" Multiplication table of a finite monoid; GROUP indicates validated inverses."]#[derive(Debug,Clone)]pub struct OperationTable<const GROUP:bool=false>{table:Vec<Vec<usize>>,generators:Vec<usize>,unit:usize,inverse:Vec<usize>}impl OperationTable{#[doc=" Builds from right generator transitions in O(N^2 + NK) time."]#[doc=" The input must be a monoid with identity 0, from which all elements are reachable."]#[doc=" Element IDs are preserved."]pub fn from_transitions(transitions:&[Vec<usize>])->Self{let n=transitions.len();let mut parent=vec![(usize::MAX,usize::MAX);n];parent[0]=(0,0);let mut order=vec![0];let mut i=0;while i<order.len(){let a=order[i];for(g,&b)in transitions[a].iter().enumerate(){if parent[b].0==usize::MAX{parent[b]=(a,g);order.push(b);}}i+=1;}assert_eq!(order.len(),n,"all elements must be reachable from identity");let table=(0..n).map(|a|{let mut row=vec![0;n];row[0]=a;for&b in&order[1..]{let(p,g)=parent[b];row[b]=transitions[row[p]][g];}row}).collect();Self{table,generators:transitions[0].clone(),unit:0,inverse:Vec::new()}}#[doc=" Builds from an associative operation on `0..n` and finds its two-sided identity."]#[doc=" Each element ID also serves as its generator ID."]#[doc=" An identity must exist. Calls f N^2 times and takes O(N^2) space and time."]pub fn from_fn<F>(n:usize,mut f:F)->Self where F:FnMut(usize,usize)->usize{let table:Vec<Vec<_>>=(0..n).map(|a|(0..n).map(|b|f(a,b)).collect()).collect();let unit=(0..n).find(|&e|(0..n).all(|a|table[e][a]==a&&table[a][e]==a)).expect("a two-sided identity must exist");Self{table,generators:(0..n).collect(),unit,inverse:Vec::new()}}#[doc=" Checks all two-sided inverses in O(N^2) time."]#[doc=" Returns the original table if any element is not invertible."]pub fn into_group(self)->Result<OperationTable<true>,Self>{let n=self.table.len();let mut inverse=Vec::with_capacity(n);for a in 0..n{let b=(0..n).find(|&b|self.table[a][b]==self.unit&&self.table[b][a]==self.unit);let Some(b)=b else{return Err(self);};inverse.push(b);}Ok(OperationTable{table:self.table,generators:self.generators,unit:self.unit,inverse})}}#[doc=" Uses the thread-local OperationTable supplied by S."]#[doc=" Keep that table unchanged while its elements or data structures are in use."]pub struct TableOperation<S>{_marker:PhantomData<fn()->S>}impl<S,const GROUP:bool>TableOperation<S>where S:AssociatedValue<T=OperationTable<GROUP>>{#[doc=" Converts a generator ID to its monoid element ID."]pub fn from_generator(generator:usize)->usize{S::with(|table|table.generators[generator])}#[doc=" Evaluates generator IDs in order; an empty sequence gives the identity."]pub fn from_generators<I>(generators:I)->usize where I:IntoIterator<Item=usize>{S::with(|table|{generators.into_iter().fold(table.unit,|a,g|table.table[a][table.generators[g]])})}}impl<S,const GROUP:bool>Magma for TableOperation<S>where S:AssociatedValue<T=OperationTable<GROUP>>{type T=usize;fn operate(x:&Self::T,y:&Self::T)->Self::T{S::with(|table|table.table[*x][*y])}}impl<S,const GROUP:bool>Associative for TableOperation<S>where S:AssociatedValue<T=OperationTable<GROUP>>{}impl<S,const GROUP:bool>Unital for TableOperation<S>where S:AssociatedValue<T=OperationTable<GROUP>>{fn unit()->Self::T{S::with(|table|table.unit)}}impl<S>Invertible for TableOperation<S>where S:AssociatedValue<T=OperationTable<true>>{fn inverse(x:&Self::T)->Self::T{S::with(|table|table.inverse[*x])}}}
// codesnip-guard: AssociatedValue
#[cfg_attr(any(),rustfmt::skip)]pub use self::associated_value::AssociatedValue;#[cfg_attr(any(),rustfmt::skip)]mod associated_value{#[doc=" Trait for a modifiable value associated with a type."]pub trait AssociatedValue{#[doc=" Type of value."]type T:'static+Clone;unsafe fn __local_key()->&'static std::thread::LocalKey<std::cell::Cell<Self::T>>;#[inline]fn get()->Self::T{Self::with(Clone::clone)}#[inline]fn set(x:Self::T){unsafe{Self::__local_key().with(|cell|cell.set(x))}}#[inline]fn replace(x:Self::T)->Self::T{unsafe{Self::__local_key().with(|cell|cell.replace(x))}}#[inline]fn with<F,R>(f:F)->R where F:FnOnce(&Self::T)->R{unsafe{Self::__local_key().with(|cell|f(&*cell.as_ptr()))}}#[inline]fn modify<F,R>(f:F)->R where F:FnOnce(&mut Self::T)->R{unsafe{Self::__local_key().with(|cell|f(&mut*cell.as_ptr()))}}}#[doc=" Implement [`AssociatedValue`]."]#[doc=""]#[doc=" [`AssociatedValue`]: super::AssociatedValue"]#[doc=""]#[doc=" # Examples"]#[doc=""]#[doc=" ```"]#[doc=" use competitive::tools::AssociatedValue;"]#[doc=" enum X {}"]#[doc=" competitive::impl_assoc_value!(X, usize, 1);"]#[doc=" assert_eq!(X::get(), 1);"]#[doc=" X::set(10);"]#[doc=" assert_eq!(X::get(), 10);"]#[doc=" ```"]#[doc=""]#[doc=" init with `Default::default()`"]#[doc=""]#[doc=" ```"]#[doc=" use competitive::tools::AssociatedValue;"]#[doc=" enum X {}"]#[doc=" competitive::impl_assoc_value!(X, usize);"]#[doc=" assert_eq!(X::get(), Default::default());"]#[doc=" ```"]#[macro_export]macro_rules!impl_assoc_value{($name:ident,$t:ty)=>{$crate::impl_assoc_value!($name,$t,Default::default());};($name:ident,$t:ty,$e:expr)=>{impl AssociatedValue for$name{type T=$t;#[inline]unsafe fn __local_key()->&'static::std::thread::LocalKey<::std::cell::Cell<Self::T>>{::std::thread_local!(static __LOCAL_KEY: ::std::cell::Cell<$t> =::std::cell::Cell::new($e));&__LOCAL_KEY}}};}}
// codesnip-guard: algebra
#[cfg_attr(any(),rustfmt::skip)]pub use self::magma::*;#[cfg_attr(any(),rustfmt::skip)]mod magma{#![doc=" algebraic traits"]#[doc=" binary operaion: $T \\circ T \\to T$"]pub trait Magma{#[doc=" type of operands: $T$"]type T:Clone;#[doc=" binary operaion: $\\circ$"]fn operate(x:&Self::T,y:&Self::T)->Self::T;fn reverse_operate(x:&Self::T,y:&Self::T)->Self::T{Self::operate(y,x)}fn operate_assign(x:&mut Self::T,y:&Self::T){*x=Self::operate(x,y);}}#[doc=" $\\forall a,\\forall b,\\forall c \\in T, (a \\circ b) \\circ c = a \\circ (b \\circ c)$"]pub trait Associative:Magma{}#[doc=" associative binary operation"]pub trait SemiGroup:Magma+Associative{}impl<S>SemiGroup for S where S:Magma+Associative{}#[doc=" $\\exists e \\in T, \\forall a \\in T, e \\circ a = a \\circ e = a$"]pub trait Unital:Magma{#[doc=" identity element: $e$"]fn unit()->Self::T;fn is_unit(x:&Self::T)->bool where Self::T:PartialEq{x==&Self::unit()}fn set_unit(x:&mut Self::T){*x=Self::unit();}}pub trait ExpBits{type Iter:Iterator<Item=bool>;fn bits(self)->Self::Iter;}pub trait SignedExpBits{type T:ExpBits;fn neg_and_bits(self)->(bool,Self::T);}pub struct Bits<T>{n:T}macro_rules!impl_exp_bits_for_uint{($($t:ty)*)=>{$(impl Iterator for Bits<$t>{type Item=bool;fn next(&mut self)->Option<bool>{if self.n==0{None}else{let bit=(self.n&1)==1;self.n>>=1;Some(bit)}}}impl ExpBits for$t{type Iter=Bits<$t>;fn bits(self)->Self::Iter{Bits{n:self}}}impl SignedExpBits for$t{type T=$t;fn neg_and_bits(self)->(bool,Self::T){(false,self)}})*};}impl_exp_bits_for_uint!(u8 u16 u32 u64 u128 usize);macro_rules!impl_signed_exp_bits_for_sint{($($s:ty,$u:ty;)*)=>{$(impl SignedExpBits for$s{type T=$u;fn neg_and_bits(self)->(bool,Self::T){(self<0,self.unsigned_abs())}})*};}impl_signed_exp_bits_for_sint!(i8,u8;i16,u16;i32,u32;i64,u64;i128,u128;isize,usize;);#[doc=" associative binary operation and an identity element"]pub trait Monoid:SemiGroup+Unital{#[doc=" binary exponentiation: $x^n = x\\circ\\ddots\\circ x$"]fn pow<E>(mut x:Self::T,exp:E)->Self::T where E:ExpBits{let mut bits=exp.bits();let Some(first)=bits.next()else{return Self::unit();};let mut res=if first{x.clone()}else{Self::unit()};for bit in bits{x=Self::operate(&x,&x);if bit{res=Self::operate(&res,&x);}}res}fn fold<I>(iter:I)->Self::T where I:IntoIterator<Item=Self::T>{let mut iter=iter.into_iter();if let Some(item)=iter.next(){iter.fold(item,|acc,x|Self::operate(&acc,&x))}else{Self::unit()}}}impl<M>Monoid for M where M:SemiGroup+Unital{}#[doc=" $\\exists e \\in T, \\forall a \\in T, \\exists b,c \\in T, b \\circ a = a \\circ c = e$"]pub trait Invertible:Magma+Unital{#[doc=" $a$ where $a \\circ x = e$"]fn inverse(x:&Self::T)->Self::T;fn rinv_operate(x:&Self::T,y:&Self::T)->Self::T{Self::operate(x,&Self::inverse(y))}fn rinv_operate_assign(x:&mut Self::T,y:&Self::T){*x=Self::rinv_operate(x,y);}}#[doc=" associative binary operation and an identity element and inverse elements"]pub trait Group:Monoid+Invertible{fn signed_pow<E>(x:Self::T,exp:E)->Self::T where E:SignedExpBits{let(neg,exp)=E::neg_and_bits(exp);let res=Self::pow(x,exp);if neg{Self::inverse(&res)}else{res}}}impl<G>Group for G where G:Monoid+Invertible{}#[doc=" $\\forall a,\\forall b \\in T, a \\circ b = b \\circ a$"]pub trait Commutative:Magma{}#[doc=" commutative monoid"]pub trait AbelianMonoid:Monoid+Commutative{}impl<M>AbelianMonoid for M where M:Monoid+Commutative{}#[doc=" commutative group"]pub trait AbelianGroup:Group+Commutative{}impl<G>AbelianGroup for G where G:Group+Commutative{}#[doc=" $\\forall a \\in T, a \\circ a = a$"]pub trait Idempotent:Magma{}#[doc=" idempotent monoid"]pub trait IdempotentMonoid:Monoid+Idempotent{}impl<M>IdempotentMonoid for M where M:Monoid+Idempotent{}#[macro_export]macro_rules!monoid_fold{($m:ty)=>{<$m as Unital>::unit()};($m:ty,)=>{<$m as Unital>::unit()};($m:ty,$f:expr)=>{$f};($m:ty,$f:expr,$($ff:expr),*)=>{<$m as Magma>::operate(&($f),&monoid_fold!($m,$($ff),*))};}#[macro_export]macro_rules!define_monoid{($Name:ident,$t:ty,|$x:ident,$y:ident|$op:expr,$unit:expr)=>{struct$Name;impl Magma for$Name{type T=$t;fn operate($x:&Self::T,$y:&Self::T)->Self::T{$op}}impl Unital for$Name{fn unit()->Self::T{$unit}}impl Associative for$Name{}};}}