Struct Xorshift

Source

pub struct Xorshift {
    y: u64,
}

Fields§

§y: u64

Implementations§

Source §

impl Xorshift

Source

pub fn random<T, R>(&mut self, spec: R) -> T
where R: RandomSpec<T>,

Examples found in repository ?

crates/competitive/src/tools/random_generator.rs (line 75)

74    fn rand(&self, rng: &mut Xorshift) -> i128 {
75        rng.random::<u128, _>(..) as i128
76    }
77}
78
79macro_rules! impl_random_spec_ranges {
80    ($($u:ident $i:ident)*) => {
81        $(
82            impl RandomSpec<$u> for Range<$u> {
83                fn rand(&self, rng: &mut Xorshift) -> $u {
84                    assert!(self.start < self.end);
85                    let len = self.end - self.start;
86                    (self.start + rng.random::<$u, _>(..) % len)
87                }
88            }
89            impl RandomSpec<$i> for Range<$i> {
90                fn rand(&self, rng: &mut Xorshift) -> $i {
91                    assert!(self.start < self.end);
92                    let len = self.end.abs_diff(self.start);
93                    self.start.wrapping_add_unsigned(rng.random::<$u, _>(..) % len)
94                }
95            }
96            impl RandomSpec<$u> for RangeFrom<$u> {
97                fn rand(&self, rng: &mut Xorshift) -> $u {
98                    let len = ($u::MAX - self.start).wrapping_add(1);
99                    let x = rng.random::<$u, _>(..);
100                    self.start + if len != 0 { x % len } else { x }
101                }
102            }
103            impl RandomSpec<$i> for RangeFrom<$i> {
104                fn rand(&self, rng: &mut Xorshift) -> $i {
105                    let len = ($i::MAX.abs_diff(self.start)).wrapping_add(1);
106                    let x = rng.random::<$u, _>(..);
107                    self.start.wrapping_add_unsigned(if len != 0 { x % len } else { x })
108                }
109            }
110            impl RandomSpec<$u> for RangeInclusive<$u> {
111                fn rand(&self, rng: &mut Xorshift) -> $u {
112                    assert!(self.start() <= self.end());
113                    let len = (self.end() - self.start()).wrapping_add(1);
114                    let x = rng.random::<$u, _>(..);
115                    self.start() + if len != 0 { x % len } else { x }
116                }
117            }
118            impl RandomSpec<$i> for RangeInclusive<$i> {
119                fn rand(&self, rng: &mut Xorshift) -> $i {
120                    assert!(self.start() <= self.end());
121                    let len = (self.end().abs_diff(*self.start())).wrapping_add(1);
122                    let x = rng.random::<$u, _>(..);
123                    self.start().wrapping_add_unsigned(if len != 0 { x % len } else { x })
124                }
125            }
126            impl RandomSpec<$u> for RangeTo<$u> {
127                fn rand(&self, rng: &mut Xorshift) -> $u {
128                    let len = self.end;
129                    rng.random::<$u, _>(..) % len
130                }
131            }
132            impl RandomSpec<$i> for RangeTo<$i> {
133                fn rand(&self, rng: &mut Xorshift) -> $i {
134                    let len = self.end.abs_diff($i::MIN);
135                    $i::MIN.wrapping_add_unsigned(rng.random::<$u, _>(..) % len)
136                }
137            }
138            impl RandomSpec<$u> for RangeToInclusive<$u> {
139                fn rand(&self, rng: &mut Xorshift) -> $u {
140                    let len = (self.end).wrapping_add(1);
141                    let x = rng.random::<$u, _>(..);
142                    if len != 0 { x % len } else { x }
143                }
144            }
145            impl RandomSpec<$i> for RangeToInclusive<$i> {
146                fn rand(&self, rng: &mut Xorshift) -> $i {
147                    let len = (self.end.abs_diff($i::MIN)).wrapping_add(1);
148                    let x = rng.random::<$u, _>(..);
149                    $i::MIN.wrapping_add_unsigned(if len != 0 { x % len } else { x })
150                }
151            }
152        )*
153    };
154}
155impl_random_spec_ranges!(u8 i8 u16 i16 u32 i32 u64 i64 u128 i128 usize isize);
156
157macro_rules! impl_random_spec_tuple {
158    ($($T:ident)*, $($R:ident)*, $($v:ident)*) => {
159        impl<$($T),*, $($R),*> RandomSpec<($($T,)*)> for ($($R,)*)
160        where
161            $($R: RandomSpec<$T>),*
162        {
163            fn rand(&self, rng: &mut Xorshift) -> ($($T,)*) {
164                let ($($v,)*) = self;
165                ($(($v).rand(rng),)*)
166            }
167        }
168    };
169}
170impl_random_spec_tuple!(A, RA, a);
171impl_random_spec_tuple!(A B, RA RB, a b);
172impl_random_spec_tuple!(A B C, RA RB RC, a b c);
173impl_random_spec_tuple!(A B C D, RA RB RC RD, a b c d);
174impl_random_spec_tuple!(A B C D E, RA RB RC RD RE, a b c d e);
175impl_random_spec_tuple!(A B C D E F, RA RB RC RD RE RF, a b c d e f);
176impl_random_spec_tuple!(A B C D E F G, RA RB RC RD RE RF RG, a b c d e f g);
177impl_random_spec_tuple!(A B C D E F G H, RA RB RC RD RE RF RG RH, a b c d e f g h);
178impl_random_spec_tuple!(A B C D E F G H I, RA RB RC RD RE RF RG RH RI, a b c d e f g h i);
179impl_random_spec_tuple!(A B C D E F G H I J, RA RB RC RD RE RF RG RH RI RJ, a b c d e f g h i j);
180
181macro_rules! impl_random_spec_primitive {
182    ($($t:ty)*) => {
183        $(impl RandomSpec<$t> for $t {
184            fn rand(&self, _rng: &mut Xorshift) -> $t {
185                *self
186            }
187        })*
188    };
189}
190impl_random_spec_primitive!(() u8 u16 u32 u64 u128 usize i8 i16 i32 i64 i128 isize bool char);
191
192impl<T, R> RandomSpec<T> for &R
193where
194    R: RandomSpec<T>,
195{
196    fn rand(&self, rng: &mut Xorshift) -> T {
197        <R as RandomSpec<T>>::rand(self, rng)
198    }
199}
200impl<T, R> RandomSpec<T> for &mut R
201where
202    R: RandomSpec<T>,
203{
204    fn rand(&self, rng: &mut Xorshift) -> T {
205        <R as RandomSpec<T>>::rand(self, rng)
206    }
207}
208
209#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
210/// Left-close Right-open No Empty Segment
211pub struct NotEmptySegment<T>(pub T);
212impl<T> RandomSpec<(usize, usize)> for NotEmptySegment<T>
213where
214    T: RandomSpec<usize>,
215{
216    fn rand(&self, rng: &mut Xorshift) -> (usize, usize) {
217        let n = rng.random(&self.0) as u64;
218        let k = randint_uniform(rng, n);
219        let l = randint_uniform(rng, n - k) as usize;
220        (l, l + k as usize + 1)
221    }
222}
223
224#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
225/// Left-close Right-open Segment
226pub struct WithEmptySegment<T>(pub T);
227impl<T> RandomSpec<(usize, usize)> for WithEmptySegment<T>
228where
229    T: RandomSpec<usize>,
230{
231    fn rand(&self, rng: &mut Xorshift) -> (usize, usize) {
232        let n = rng.random(&self.0) as u64;
233        let k = randint_uniform(rng, n + 1);
234        let l = randint_uniform(rng, n - k + 1) as usize;
235        (l, l + k as usize)
236    }
237}
238
239#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
240pub struct RandRange<Q, T> {
241    data: Q,
242    _marker: PhantomData<fn() -> T>,
243}
244impl<Q, T> RandRange<Q, T> {
245    pub fn new(data: Q) -> Self {
246        Self {
247            data,
248            _marker: PhantomData,
249        }
250    }
251}
252impl<Q, T> RandomSpec<(Bound<T>, Bound<T>)> for RandRange<Q, T>
253where
254    Q: RandomSpec<T>,
255    T: Ord,
256{
257    fn rand(&self, rng: &mut Xorshift) -> (Bound<T>, Bound<T>) {
258        let mut l = rng.random(&self.data);
259        let mut r = rng.random(&self.data);
260        if l > r {
261            swap(&mut l, &mut r);
262        }
263        (
264            match rng.rand(3) {
265                0 => Bound::Excluded(l),
266                1 => Bound::Included(l),
267                _ => Bound::Unbounded,
268            },
269            match rng.rand(3) {
270                0 => Bound::Excluded(r),
271                1 => Bound::Included(r),
272                _ => Bound::Unbounded,
273            },
274        )
275    }

More examples

Hide additional examples

crates/competitive/src/num/mint/mod.rs (line 96)

95        fn rand(&self, rng: &mut Xorshift) -> MInt<M> {
96            MInt::<M>::new_unchecked(rng.random(..M::get_mod()))
97        }

crates/competitive/src/tree/generator.rs (line 8)

7    fn rand(&self, rng: &mut Xorshift) -> UndirectedSparseGraph {
8        let n = rng.random(&self.0);
9        let edges = from_prufer_sequence(
10            n,
11            &rng.random_iter(0..n)
12                .take(n.saturating_sub(2))
13                .collect::<Vec<usize>>(),
14        );
15        UndirectedSparseGraph::from_edges(n, edges)
16    }
17}
18
19pub struct PathTree<T>(pub T);
20
21impl<T: RandomSpec<usize>> RandomSpec<UndirectedSparseGraph> for PathTree<T> {
22    fn rand(&self, rng: &mut Xorshift) -> UndirectedSparseGraph {
23        let n = rng.random(&self.0);
24        let edges = (1..n).map(|u| (u - 1, u)).collect();
25        UndirectedSparseGraph::from_edges(n, edges)
26    }
27}
28
29pub struct StarTree<T>(pub T);
30
31impl<T: RandomSpec<usize>> RandomSpec<UndirectedSparseGraph> for StarTree<T> {
32    fn rand(&self, rng: &mut Xorshift) -> UndirectedSparseGraph {
33        let n = rng.random(&self.0);
34        let edges = (1..n).map(|u| (0, u)).collect();
35        UndirectedSparseGraph::from_edges(n, edges)
36    }
37}
38
39pub struct MixedTree<T>(pub T);
40
41impl<T: RandomSpec<usize>> RandomSpec<UndirectedSparseGraph> for MixedTree<T> {
42    fn rand(&self, rng: &mut Xorshift) -> UndirectedSparseGraph {
43        fn rand_inner(n: usize, rng: &mut Xorshift) -> Vec<(usize, usize)> {
44            let mut edges = Vec::with_capacity(n.saturating_sub(1));
45            if n >= 2 {
46                let k = rng.random(1..n);
47                for n in [k, n - k].iter().cloned() {
48                    let ty = rng.rand(6);
49                    edges.extend(match ty {
50                        0 => from_prufer_sequence(
51                            n,
52                            &rng.random_iter(0..n)
53                                .take(n.saturating_sub(2))
54                                .collect::<Vec<usize>>(),
55                        ),
56                        1 => (1..n).map(|u| (u - 1, u)).collect(),
57                        2 => (1..n).map(|u| (0, u)).collect(),
58                        _ => rand_inner(n, rng),
59                    });
60                }
61                for (u, v) in edges[k - 1..].iter_mut() {
62                    *u += k;
63                    *v += k;
64                }
65                edges.push((rng.random(0..k), rng.random(k..n)));
66            }
67            edges
68        }
69        let n = rng.random(&self.0);
70        let edges = rand_inner(n, rng);
71        UndirectedSparseGraph::from_edges(n, edges)
72    }

crates/competitive/src/algorithm/automata_learning.rs (line 289)

277pub fn random_sampling(
278    sigma: usize,
279    len_spec: impl RandomSpec<usize>,
280    seconds: f64,
281) -> impl Iterator<Item = Vec<usize>> {
282    assert_ne!(sigma, 0, "Sigma must be greater than 0");
283    let now = Instant::now();
284    let mut rng = Xorshift::new();
285    from_fn(move || {
286        if now.elapsed().as_secs_f64() > seconds {
287            None
288        } else {
289            let n = rng.random(&len_spec);
290            Some(rng.random_iter(0..sigma).take(n).collect())
291        }
292    })
293}

Source

pub fn random_iter<T, R>(&mut self, spec: R) -> RandIter<'_, T, R> ⓘ
where R: RandomSpec<T>,

Examples found in repository ?

crates/competitive/src/tree/generator.rs (line 11)

7    fn rand(&self, rng: &mut Xorshift) -> UndirectedSparseGraph {
8        let n = rng.random(&self.0);
9        let edges = from_prufer_sequence(
10            n,
11            &rng.random_iter(0..n)
12                .take(n.saturating_sub(2))
13                .collect::<Vec<usize>>(),
14        );
15        UndirectedSparseGraph::from_edges(n, edges)
16    }
17}
18
19pub struct PathTree<T>(pub T);
20
21impl<T: RandomSpec<usize>> RandomSpec<UndirectedSparseGraph> for PathTree<T> {
22    fn rand(&self, rng: &mut Xorshift) -> UndirectedSparseGraph {
23        let n = rng.random(&self.0);
24        let edges = (1..n).map(|u| (u - 1, u)).collect();
25        UndirectedSparseGraph::from_edges(n, edges)
26    }
27}
28
29pub struct StarTree<T>(pub T);
30
31impl<T: RandomSpec<usize>> RandomSpec<UndirectedSparseGraph> for StarTree<T> {
32    fn rand(&self, rng: &mut Xorshift) -> UndirectedSparseGraph {
33        let n = rng.random(&self.0);
34        let edges = (1..n).map(|u| (0, u)).collect();
35        UndirectedSparseGraph::from_edges(n, edges)
36    }
37}
38
39pub struct MixedTree<T>(pub T);
40
41impl<T: RandomSpec<usize>> RandomSpec<UndirectedSparseGraph> for MixedTree<T> {
42    fn rand(&self, rng: &mut Xorshift) -> UndirectedSparseGraph {
43        fn rand_inner(n: usize, rng: &mut Xorshift) -> Vec<(usize, usize)> {
44            let mut edges = Vec::with_capacity(n.saturating_sub(1));
45            if n >= 2 {
46                let k = rng.random(1..n);
47                for n in [k, n - k].iter().cloned() {
48                    let ty = rng.rand(6);
49                    edges.extend(match ty {
50                        0 => from_prufer_sequence(
51                            n,
52                            &rng.random_iter(0..n)
53                                .take(n.saturating_sub(2))
54                                .collect::<Vec<usize>>(),
55                        ),
56                        1 => (1..n).map(|u| (u - 1, u)).collect(),
57                        2 => (1..n).map(|u| (0, u)).collect(),
58                        _ => rand_inner(n, rng),
59                    });
60                }
61                for (u, v) in edges[k - 1..].iter_mut() {
62                    *u += k;
63                    *v += k;
64                }
65                edges.push((rng.random(0..k), rng.random(k..n)));
66            }
67            edges
68        }

More examples

Hide additional examples

crates/competitive/src/algorithm/automata_learning.rs (line 290)

277pub fn random_sampling(
278    sigma: usize,
279    len_spec: impl RandomSpec<usize>,
280    seconds: f64,
281) -> impl Iterator<Item = Vec<usize>> {
282    assert_ne!(sigma, 0, "Sigma must be greater than 0");
283    let now = Instant::now();
284    let mut rng = Xorshift::new();
285    from_fn(move || {
286        if now.elapsed().as_secs_f64() > seconds {
287            None
288        } else {
289            let n = rng.random(&len_spec);
290            Some(rng.random_iter(0..sigma).take(n).collect())
291        }
292    })
293}

Source §

impl Xorshift

Source

pub fn new_with_seed(seed: u64) -> Self

Examples found in repository ?

crates/competitive/src/tools/xorshift.rs (line 18)

17    pub fn new() -> Self {
18        Xorshift::new_with_seed(RandomState::new().build_hasher().finish())
19    }
20
21    pub fn rand64(&mut self) -> u64 {
22        self.y ^= self.y << 5;
23        self.y ^= self.y >> 17;
24        self.y ^= self.y << 11;
25        self.y
26    }
27
28    pub fn rand(&mut self, k: u64) -> u64 {
29        self.rand64() % k
30    }
31
32    pub fn rands(&mut self, k: u64, n: usize) -> Vec<u64> {
33        repeat_with(|| self.rand(k)).take(n).collect()
34    }
35
36    pub fn randf(&mut self) -> f64 {
37        const UPPER_MASK: u64 = 0x3FF0_0000_0000_0000;
38        const LOWER_MASK: u64 = 0x000F_FFFF_FFFF_FFFF;
39        let x = self.rand64();
40        let tmp = UPPER_MASK | (x & LOWER_MASK);
41        let result: f64 = f64::from_bits(tmp);
42        f64::from_bits(f64::to_bits(result - 1.0) ^ (x >> 63))
43    }
44
45    pub fn gen_bool(&mut self, p: f64) -> bool {
46        self.randf() < p
47    }
48
49    pub fn shuffle<T>(&mut self, slice: &mut [T]) {
50        let mut n = slice.len();
51        while n > 1 {
52            let i = self.rand(n as _) as usize;
53            n -= 1;
54            slice.swap(i, n);
55        }
56    }
57}
58
59impl Default for Xorshift {
60    fn default() -> Self {
61        Xorshift::new_with_seed(0x2b99_2ddf_a232_49d6)
62    }

More examples

Hide additional examples

crates/competitive/src/tree/tree_hash.rs (line 51)

48    pub fn with_seed(seed: u64) -> Self {
49        Self {
50            rv: Vec::new(),
51            rng: Xorshift::new_with_seed(seed),
52        }
53    }

crates/competitive/src/heuristic/simulated_annealing.rs (line 30)

19    fn default() -> Self {
20        let now = std::time::Instant::now();
21        let log_table = (0..Self::LOG_TABLE_SIZE)
22            .map(|i| ((i * 2 + 1) as f64 / (Self::LOG_TABLE_SIZE * 2) as f64).ln())
23            .collect();
24        Self {
25            iter_count: 0,
26            now,
27            time: 0.,
28            temperture: 3e3,
29            log_table,
30            rand: Xorshift::new_with_seed(Self::SEED),
31            is_maximize: true,
32            start_temp: 3e3,
33            end_temp: 1e-8,
34            time_limit: 1.99,
35            update_interval: 0xff,
36        }
37    }

Source

pub fn new() -> Self

Examples found in repository ?

crates/competitive/src/string/rolling_hash.rs (line 14)

13    fn init(len: usize) {
14        let mut rng = Xorshift::new();
15        Self::init_with_rng(len, &mut rng);
16    }

More examples

Hide additional examples

crates/competitive/src/tree/tree_hash.rs (line 45)

42    pub fn new() -> Self {
43        Self {
44            rv: Vec::new(),
45            rng: Xorshift::new(),
46        }
47    }

crates/competitive/src/string/wildcard_pattern_matching.rs (line 4)

3pub fn wildcard_pattern_matching(p: &[u8], s: &[u8]) -> Vec<bool> {
4    wildcard_pattern_matching_with_rng(p, s, &mut Xorshift::new())
5}

crates/competitive/src/data_structure/implicit_treap.rs (line 238)

234    fn default() -> Self {
235        Self {
236            root: None,
237            length: 0,
238            rng: Xorshift::new(),
239            allocator: ManuallyDrop::new(A::default()),
240            _marker: PhantomData,
241        }
242    }
243}
244
245impl<T, A> Drop for ImplicitTreap<T, A>
246where
247    T: LazyMapMonoid,
248    A: Allocator<ImplicitTreapNode<T>>,
249{
250    fn drop(&mut self) {
251        unsafe {
252            if let Some(root) = self.root.take() {
253                root.into_dying().drop_all(self.allocator.deref_mut());
254            }
255            ManuallyDrop::drop(&mut self.allocator);
256        }
257    }
258}
259
260impl<T> ImplicitTreap<T>
261where
262    T: LazyMapMonoid,
263{
264    pub fn new() -> Self {
265        Self::default()
266    }
267
268    pub fn with_capacity(capacity: usize) -> Self {
269        Self {
270            root: None,
271            length: 0,
272            rng: Xorshift::new(),
273            allocator: ManuallyDrop::new(MemoryPool::with_capacity(capacity)),
274            _marker: PhantomData,
275        }
276    }

crates/competitive/src/data_structure/treap.rs (line 252)

248    fn default() -> Self {
249        Self {
250            root: None,
251            node_id_manager: Default::default(),
252            rng: Xorshift::new(),
253            allocator: ManuallyDrop::new(A::default()),
254            _marker: PhantomData,
255        }
256    }

crates/competitive/src/algorithm/automata_learning.rs (line 284)

277pub fn random_sampling(
278    sigma: usize,
279    len_spec: impl RandomSpec<usize>,
280    seconds: f64,
281) -> impl Iterator<Item = Vec<usize>> {
282    assert_ne!(sigma, 0, "Sigma must be greater than 0");
283    let now = Instant::now();
284    let mut rng = Xorshift::new();
285    from_fn(move || {
286        if now.elapsed().as_secs_f64() > seconds {
287            None
288        } else {
289            let n = rng.random(&len_spec);
290            Some(rng.random_iter(0..sigma).take(n).collect())
291        }
292    })
293}

Additional examples can be found in:

Source

pub fn rand64(&mut self) -> u64

Examples found in repository ?

crates/competitive/src/tools/xorshift.rs (line 29)

28    pub fn rand(&mut self, k: u64) -> u64 {
29        self.rand64() % k
30    }
31
32    pub fn rands(&mut self, k: u64, n: usize) -> Vec<u64> {
33        repeat_with(|| self.rand(k)).take(n).collect()
34    }
35
36    pub fn randf(&mut self) -> f64 {
37        const UPPER_MASK: u64 = 0x3FF0_0000_0000_0000;
38        const LOWER_MASK: u64 = 0x000F_FFFF_FFFF_FFFF;
39        let x = self.rand64();
40        let tmp = UPPER_MASK | (x & LOWER_MASK);
41        let result: f64 = f64::from_bits(tmp);
42        f64::from_bits(f64::to_bits(result - 1.0) ^ (x >> 63))
43    }

More examples

Hide additional examples

crates/competitive/src/tools/random_generator.rs (line 70)

69    fn rand(&self, rng: &mut Xorshift) -> u128 {
70        ((rng.rand64() as u128) << 64) | rng.rand64() as u128
71    }
72}
73impl RandomSpec<i128> for RangeFull {
74    fn rand(&self, rng: &mut Xorshift) -> i128 {
75        rng.random::<u128, _>(..) as i128
76    }
77}
78
79macro_rules! impl_random_spec_ranges {
80    ($($u:ident $i:ident)*) => {
81        $(
82            impl RandomSpec<$u> for Range<$u> {
83                fn rand(&self, rng: &mut Xorshift) -> $u {
84                    assert!(self.start < self.end);
85                    let len = self.end - self.start;
86                    (self.start + rng.random::<$u, _>(..) % len)
87                }
88            }
89            impl RandomSpec<$i> for Range<$i> {
90                fn rand(&self, rng: &mut Xorshift) -> $i {
91                    assert!(self.start < self.end);
92                    let len = self.end.abs_diff(self.start);
93                    self.start.wrapping_add_unsigned(rng.random::<$u, _>(..) % len)
94                }
95            }
96            impl RandomSpec<$u> for RangeFrom<$u> {
97                fn rand(&self, rng: &mut Xorshift) -> $u {
98                    let len = ($u::MAX - self.start).wrapping_add(1);
99                    let x = rng.random::<$u, _>(..);
100                    self.start + if len != 0 { x % len } else { x }
101                }
102            }
103            impl RandomSpec<$i> for RangeFrom<$i> {
104                fn rand(&self, rng: &mut Xorshift) -> $i {
105                    let len = ($i::MAX.abs_diff(self.start)).wrapping_add(1);
106                    let x = rng.random::<$u, _>(..);
107                    self.start.wrapping_add_unsigned(if len != 0 { x % len } else { x })
108                }
109            }
110            impl RandomSpec<$u> for RangeInclusive<$u> {
111                fn rand(&self, rng: &mut Xorshift) -> $u {
112                    assert!(self.start() <= self.end());
113                    let len = (self.end() - self.start()).wrapping_add(1);
114                    let x = rng.random::<$u, _>(..);
115                    self.start() + if len != 0 { x % len } else { x }
116                }
117            }
118            impl RandomSpec<$i> for RangeInclusive<$i> {
119                fn rand(&self, rng: &mut Xorshift) -> $i {
120                    assert!(self.start() <= self.end());
121                    let len = (self.end().abs_diff(*self.start())).wrapping_add(1);
122                    let x = rng.random::<$u, _>(..);
123                    self.start().wrapping_add_unsigned(if len != 0 { x % len } else { x })
124                }
125            }
126            impl RandomSpec<$u> for RangeTo<$u> {
127                fn rand(&self, rng: &mut Xorshift) -> $u {
128                    let len = self.end;
129                    rng.random::<$u, _>(..) % len
130                }
131            }
132            impl RandomSpec<$i> for RangeTo<$i> {
133                fn rand(&self, rng: &mut Xorshift) -> $i {
134                    let len = self.end.abs_diff($i::MIN);
135                    $i::MIN.wrapping_add_unsigned(rng.random::<$u, _>(..) % len)
136                }
137            }
138            impl RandomSpec<$u> for RangeToInclusive<$u> {
139                fn rand(&self, rng: &mut Xorshift) -> $u {
140                    let len = (self.end).wrapping_add(1);
141                    let x = rng.random::<$u, _>(..);
142                    if len != 0 { x % len } else { x }
143                }
144            }
145            impl RandomSpec<$i> for RangeToInclusive<$i> {
146                fn rand(&self, rng: &mut Xorshift) -> $i {
147                    let len = (self.end.abs_diff($i::MIN)).wrapping_add(1);
148                    let x = rng.random::<$u, _>(..);
149                    $i::MIN.wrapping_add_unsigned(if len != 0 { x % len } else { x })
150                }
151            }
152        )*
153    };
154}
155impl_random_spec_ranges!(u8 i8 u16 i16 u32 i32 u64 i64 u128 i128 usize isize);
156
157macro_rules! impl_random_spec_tuple {
158    ($($T:ident)*, $($R:ident)*, $($v:ident)*) => {
159        impl<$($T),*, $($R),*> RandomSpec<($($T,)*)> for ($($R,)*)
160        where
161            $($R: RandomSpec<$T>),*
162        {
163            fn rand(&self, rng: &mut Xorshift) -> ($($T,)*) {
164                let ($($v,)*) = self;
165                ($(($v).rand(rng),)*)
166            }
167        }
168    };
169}
170impl_random_spec_tuple!(A, RA, a);
171impl_random_spec_tuple!(A B, RA RB, a b);
172impl_random_spec_tuple!(A B C, RA RB RC, a b c);
173impl_random_spec_tuple!(A B C D, RA RB RC RD, a b c d);
174impl_random_spec_tuple!(A B C D E, RA RB RC RD RE, a b c d e);
175impl_random_spec_tuple!(A B C D E F, RA RB RC RD RE RF, a b c d e f);
176impl_random_spec_tuple!(A B C D E F G, RA RB RC RD RE RF RG, a b c d e f g);
177impl_random_spec_tuple!(A B C D E F G H, RA RB RC RD RE RF RG RH, a b c d e f g h);
178impl_random_spec_tuple!(A B C D E F G H I, RA RB RC RD RE RF RG RH RI, a b c d e f g h i);
179impl_random_spec_tuple!(A B C D E F G H I J, RA RB RC RD RE RF RG RH RI RJ, a b c d e f g h i j);
180
181macro_rules! impl_random_spec_primitive {
182    ($($t:ty)*) => {
183        $(impl RandomSpec<$t> for $t {
184            fn rand(&self, _rng: &mut Xorshift) -> $t {
185                *self
186            }
187        })*
188    };
189}
190impl_random_spec_primitive!(() u8 u16 u32 u64 u128 usize i8 i16 i32 i64 i128 isize bool char);
191
192impl<T, R> RandomSpec<T> for &R
193where
194    R: RandomSpec<T>,
195{
196    fn rand(&self, rng: &mut Xorshift) -> T {
197        <R as RandomSpec<T>>::rand(self, rng)
198    }
199}
200impl<T, R> RandomSpec<T> for &mut R
201where
202    R: RandomSpec<T>,
203{
204    fn rand(&self, rng: &mut Xorshift) -> T {
205        <R as RandomSpec<T>>::rand(self, rng)
206    }
207}
208
209#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
210/// Left-close Right-open No Empty Segment
211pub struct NotEmptySegment<T>(pub T);
212impl<T> RandomSpec<(usize, usize)> for NotEmptySegment<T>
213where
214    T: RandomSpec<usize>,
215{
216    fn rand(&self, rng: &mut Xorshift) -> (usize, usize) {
217        let n = rng.random(&self.0) as u64;
218        let k = randint_uniform(rng, n);
219        let l = randint_uniform(rng, n - k) as usize;
220        (l, l + k as usize + 1)
221    }
222}
223
224#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
225/// Left-close Right-open Segment
226pub struct WithEmptySegment<T>(pub T);
227impl<T> RandomSpec<(usize, usize)> for WithEmptySegment<T>
228where
229    T: RandomSpec<usize>,
230{
231    fn rand(&self, rng: &mut Xorshift) -> (usize, usize) {
232        let n = rng.random(&self.0) as u64;
233        let k = randint_uniform(rng, n + 1);
234        let l = randint_uniform(rng, n - k + 1) as usize;
235        (l, l + k as usize)
236    }
237}
238
239#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
240pub struct RandRange<Q, T> {
241    data: Q,
242    _marker: PhantomData<fn() -> T>,
243}
244impl<Q, T> RandRange<Q, T> {
245    pub fn new(data: Q) -> Self {
246        Self {
247            data,
248            _marker: PhantomData,
249        }
250    }
251}
252impl<Q, T> RandomSpec<(Bound<T>, Bound<T>)> for RandRange<Q, T>
253where
254    Q: RandomSpec<T>,
255    T: Ord,
256{
257    fn rand(&self, rng: &mut Xorshift) -> (Bound<T>, Bound<T>) {
258        let mut l = rng.random(&self.data);
259        let mut r = rng.random(&self.data);
260        if l > r {
261            swap(&mut l, &mut r);
262        }
263        (
264            match rng.rand(3) {
265                0 => Bound::Excluded(l),
266                1 => Bound::Included(l),
267                _ => Bound::Unbounded,
268            },
269            match rng.rand(3) {
270                0 => Bound::Excluded(r),
271                1 => Bound::Included(r),
272                _ => Bound::Unbounded,
273            },
274        )
275    }
276}
277
278#[inline]
279fn randint_uniform(rng: &mut Xorshift, k: u64) -> u64 {
280    let mut v = rng.rand64();
281    if k > 0 {
282        v %= k;
283    }
284    v
285}

crates/competitive/src/data_structure/implicit_treap.rs (line 287)

284    fn node(&mut self, key: T::Key) -> ImplicitTreapRoot<T> {
285        BstRoot::from_data(
286            ImplicitTreapData {
287                priority: self.rng.rand64(),
288                value: LazyMapElement::from_key(key),
289                size: 1,
290                rev: false,
291            },
292            self.allocator.deref_mut(),
293        )
294    }

crates/competitive/src/tree/tree_hash.rs (line 68)

65    fn hash_rec(&mut self, g: &UndirectedSparseGraph, u: usize, p: usize, d: usize) -> u64 {
66        let mut s = 1u64;
67        if self.rv.len() <= d {
68            self.rv.push(Self::mersenne_mod(self.rng.rand64()));
69        }
70        for a in g.neighbors(u) {
71            if a.to != p {
72                s = Self::mersenne_mul_mod(s, self.hash_rec(g, a.to, u, d + 1));
73            }
74        }
75        s += self.rv[d];
76        if s >= Self::MOD {
77            s -= Self::MOD;
78        }
79        s
80    }

crates/competitive/src/math/mint_matrix.rs (line 29)

24    fn determinant_linear(mut self, other: Self) -> Option<Vec<MInt<M>>>
25    where
26        M: MIntConvert<usize> + MIntConvert<u64>,
27    {
28        let mut rng = Xorshift::new();
29        let a = MInt::from(rng.rand64());
30        let n = self.data.len();
31        for i in 0..n {
32            for j in 0..n {
33                self[i][j] += other[i][j] * a;
34            }
35        }
36        let mut f = other.determinant_linear_non_singular(self)?;
37        f.reverse();
38        Some(taylor_shift::<M>(f, -a))
39    }
40
41    fn pow_frobenius(self, k: usize) -> Self
42    where
43        M: MIntConvert<u64>,
44    {
45        assert_eq!(self.shape.0, self.shape.1);
46        let a = self.transpose();
47        let mut rng = Xorshift::new();
48        let f = loop {
49            if let Some(f) = frobenius_decomposition(&a, &mut rng) {
50                break f;
51            }
52        };
53        let fk = f.pow(k);
54        let n = f.t.shape.0;
55        if f.blocks
56            .iter()
57            .map(|p| (p.0.len() - 1).pow(2))
58            .sum::<usize>()
59            * 4
60            <= n * n
61        {
62            let mut ft = Matrix::zeros((n, n));
63            let mut first = 0;
64            for p in &f.blocks {
65                let d = p.0.len() - 1;
66                for i in first..first + d {
67                    for j in first..first + d {
68                        MInt::add_scaled_assign(&mut ft[i], &f.t[j], &fk[i][j]);
69                    }
70                }
71                first += d;
72            }
73            &f.t_inv * &ft
74        } else {
75            &(&f.t_inv * &fk) * &f.t
76        }
77    }
78}
79
80impl<M> Matrix<AddMulOperation<MInt<M>>>
81where
82    M: MIntDotProduct,
83{
84    fn determinant_linear_non_singular(mut self, mut other: Self) -> Option<Vec<MInt<M>>>
85    where
86        M: MIntDotProduct,
87    {
88        let n = self.data.len();
89        let mut f = MInt::one();
90        for d in 0..n {
91            let i = other.data.iter().position(|other| !other[d].is_zero())?;
92            if i != d {
93                self.data.swap(i, d);
94                other.data.swap(i, d);
95                f = -f;
96            }
97            f *= other[d][d];
98            let r = other[d][d].inv();
99            for j in 0..n {
100                self[d][j] *= r;
101                other[d][j] *= r;
102            }
103            assert!(other[d][d].is_one());
104            for i in d + 1..n {
105                let a = other[i][d];
106                for k in 0..n {
107                    self[i][k] = self[i][k] - a * self[d][k];
108                    other[i][k] = other[i][k] - a * other[d][k];
109                }
110            }
111            for j in d + 1..n {
112                let a = other[d][j];
113                for k in 0..n {
114                    self[k][j] = self[k][j] - a * self[k][d];
115                    other[k][j] = other[k][j] - a * other[k][d];
116                }
117            }
118        }
119        for s in self.data.iter_mut() {
120            for s in s.iter_mut() {
121                *s = -*s;
122            }
123        }
124        let mut p = self.characteristic_polynomial();
125        for p in p.iter_mut() {
126            *p *= f;
127        }
128        Some(p)
129    }
130}
131
132struct EchelonRow<M>
133where
134    M: MIntDotProduct,
135{
136    pivot: usize,
137    inv: MInt<M>,
138    row: Vec<MInt<M>>,
139}
140
141struct Polynomial<M>(Vec<MInt<M>>)
142where
143    M: MIntDotProduct;
144
145struct FrobeniusDecomposition<M>
146where
147    M: MIntDotProduct,
148{
149    t: Matrix<AddMulOperation<MInt<M>>>,
150    t_inv: Matrix<AddMulOperation<MInt<M>>>,
151    blocks: Vec<Polynomial<M>>,
152}
153
154impl<M> EchelonRow<M>
155where
156    M: MIntDotProduct,
157{
158    fn reduce(&self, row: &mut [MInt<M>]) {
159        let a = -row[self.pivot] * self.inv;
160        if a.is_zero() {
161            return;
162        }
163        let end = self.row.len();
164        MInt::add_scaled_assign(&mut row[self.pivot..end], &self.row[self.pivot..], &a);
165    }
166}
167
168fn generate_frobenius_block<M>(
169    a: &Matrix<AddMulOperation<MInt<M>>>,
170    mut v: Vec<MInt<M>>,
171    rows: &mut Vec<EchelonRow<M>>,
172    t: &mut Vec<Vec<MInt<M>>>,
173) -> Polynomial<M>
174where
175    M: MIntDotProduct,
176{
177    let n = a.shape.0;
178    loop {
179        let mut row = vec![MInt::zero(); n + rows.len() + 1];
180        let (x, c) = row.split_at_mut(n);
181        x.copy_from_slice(&v);
182        c[rows.len()] = MInt::one();
183        for r in rows.iter() {
184            r.reduce(&mut row);
185        }
186        if let Some(pivot) = row[..n].iter().position(|x| !x.is_zero()) {
187            t.push(v);
188            let u = t.last().unwrap();
189            v = a.data.iter().map(|row| MInt::dot_product(u, row)).collect();
190            rows.push(EchelonRow {
191                pivot,
192                inv: row[pivot].inv(),
193                row,
194            });
195        } else {
196            let mut p = row.split_off(n);
197            while p.last().is_some_and(|x| x.is_zero()) {
198                p.pop();
199            }
200            return Polynomial(p);
201        }
202    }
203}
204
205impl<M> Polynomial<M>
206where
207    M: MIntDotProduct,
208{
209    fn exact_div(mut self, rhs: &Self) -> Option<Self> {
210        let mut q = vec![MInt::zero(); self.0.len() - rhs.0.len() + 1];
211        let inv = rhs.0.last().unwrap().inv();
212        for i in (0..q.len()).rev() {
213            q[i] = self.0[i + rhs.0.len() - 1] * inv;
214            MInt::add_scaled_assign(&mut self.0[i..i + rhs.0.len()], &rhs.0, &-q[i]);
215        }
216        self.0.iter().all(|x| x.is_zero()).then_some(Self(q))
217    }
218
219    fn square_mod(&self, p: &Self) -> Self {
220        let d = p.0.len() - 1;
221        let mut c = vec![MInt::zero(); 2 * d - 1];
222        for (i, &x) in self.0.iter().enumerate() {
223            MInt::add_scaled_assign(&mut c[i..2 * i], &self.0[..i], &(x + x));
224            c[2 * i] += x * x;
225        }
226        for i in (d..c.len()).rev() {
227            let x = c[i];
228            MInt::add_scaled_assign(&mut c[i - d..=i], &p.0, &-x);
229        }
230        c.truncate(d);
231        Self(c)
232    }
233
234    fn x_pow_mod(&self, k: usize) -> Self {
235        let d = self.0.len() - 1;
236        if d == 1 {
237            return Self(vec![(-self.0[0]).pow(k)]);
238        }
239        let mut r = Self(vec![MInt::zero(); d]);
240        r.0[0] = MInt::one();
241        for bit in (0..usize::BITS - k.leading_zeros()).rev() {
242            r = r.square_mod(self);
243            if k >> bit & 1 != 0 {
244                let x = r.0[d - 1];
245                for i in (1..d).rev() {
246                    r.0[i] = r.0[i - 1] - x * self.0[i];
247                }
248                r.0[0] = -x * self.0[0];
249            }
250        }
251        r
252    }
253}
254
255fn frobenius_decomposition<M>(
256    a: &Matrix<AddMulOperation<MInt<M>>>,
257    rng: &mut Xorshift,
258) -> Option<FrobeniusDecomposition<M>>
259where
260    M: MIntDotProduct + MIntConvert<u64>,
261{
262    let n = a.shape.0;
263    let mut rows = Vec::with_capacity(n);
264    let mut t = Vec::with_capacity(n);
265    let mut blocks: Vec<Polynomial<M>> = Vec::new();
266    while rows.len() < n {
267        let s = rows.len();
268        let v = (0..n).map(|_| MInt::from(rng.rand64())).collect();
269        let c = generate_frobenius_block(a, v, &mut rows, &mut t);
270        if rows.len() == s {
271            continue;
272        }
273        let p = Polynomial(c.0[s..].to_vec());
274        if c.0[..s].iter().any(|x| !x.is_zero()) {
275            let q = c.exact_div(&p)?;
276            let d = rows.len() - s;
277            let mut coefficients = q.0[..s].to_vec();
278            let mut shifts = Vec::with_capacity(d);
279            for _ in 0..d {
280                shifts.push(coefficients.clone());
281                let mut first = 0;
282                for block in &blocks {
283                    let len = block.0.len() - 1;
284                    let c = &mut coefficients[first..first + len];
285                    let last = c[len - 1];
286                    for j in (1..len).rev() {
287                        c[j] = c[j - 1] - last * block.0[j];
288                    }
289                    c[0] = -last * block.0[0];
290                    first += len;
291                }
292            }
293            let shifts: Matrix<AddMulOperation<MInt<M>>> = Matrix::from_vec(shifts);
294            if d < 32 {
295                let (previous, current) = t.split_at_mut(s);
296                for (shift, row) in shifts.data.iter().zip(current) {
297                    for (factor, source) in shift.iter().zip(previous.iter()) {
298                        if !factor.is_zero() {
299                            MInt::add_scaled_assign(row, source, factor);
300                        }
301                    }
302                }
303            } else {
304                let previous = Matrix::from_vec(t[..s].to_vec());
305                let correction = &shifts * &previous;
306                for (row, correction) in t[s..].iter_mut().zip(&correction.data) {
307                    for (x, &y) in row.iter_mut().zip(correction) {
308                        *x += y;
309                    }
310                }
311            }
312            for row in &mut rows[s..] {
313                // Keep the reduced vector fixed: T_new += S*T_old gives C_old -= C_new*S.
314                let (previous, current) = row.row[n..].split_at_mut(s);
315                for (&x, shift) in current.iter().zip(&shifts.data) {
316                    MInt::add_scaled_assign(previous, shift, &-x);
317                }
318            }
319        }
320        blocks.push(p);
321    }
322
323    let mut t_inv = vec![vec![MInt::zero(); n]; n];
324    for i in (0..n).rev() {
325        let row = &rows[i];
326        let mut c = row.row[n..].to_vec();
327        c.resize(n, MInt::zero());
328        for x in &mut c {
329            *x *= row.inv;
330        }
331        for next in &rows[i + 1..] {
332            let factor = -row.row[next.pivot] * row.inv;
333            if !factor.is_zero() {
334                MInt::add_scaled_assign(&mut c, &t_inv[next.pivot], &factor);
335            }
336        }
337        t_inv[row.pivot] = c;
338    }
339    Some(FrobeniusDecomposition {
340        t: Matrix::from_vec(t),
341        t_inv: Matrix::from_vec(t_inv),
342        blocks,
343    })
344}

crates/competitive/src/math/primitive_root.rs (line 17)

3pub fn primitive_root(p: u64) -> u64 {
4    if p == 2 {
5        return 1;
6    }
7    let phi = p - 1;
8    let pf = prime_factors(phi);
9    let br = BarrettReduction::<u128>::new(p as _);
10    for g in 2..=3.min(p - 1) {
11        if check_primitive_root(g, phi, &br, &pf) {
12            return g;
13        }
14    }
15    let mut rng = Xorshift::default();
16    loop {
17        let g = ((rng.rand64() as u128 * (p - 2) as u128) >> 64) as u64 + 2;
18        if check_primitive_root(g, phi, &br, &pf) {
19            return g;
20        }
21    }
22}

Additional examples can be found in:

Source

pub fn rand(&mut self, k: u64) -> u64

Examples found in repository ?

crates/competitive/src/tools/xorshift.rs (line 33)

32    pub fn rands(&mut self, k: u64, n: usize) -> Vec<u64> {
33        repeat_with(|| self.rand(k)).take(n).collect()
34    }
35
36    pub fn randf(&mut self) -> f64 {
37        const UPPER_MASK: u64 = 0x3FF0_0000_0000_0000;
38        const LOWER_MASK: u64 = 0x000F_FFFF_FFFF_FFFF;
39        let x = self.rand64();
40        let tmp = UPPER_MASK | (x & LOWER_MASK);
41        let result: f64 = f64::from_bits(tmp);
42        f64::from_bits(f64::to_bits(result - 1.0) ^ (x >> 63))
43    }
44
45    pub fn gen_bool(&mut self, p: f64) -> bool {
46        self.randf() < p
47    }
48
49    pub fn shuffle<T>(&mut self, slice: &mut [T]) {
50        let mut n = slice.len();
51        while n > 1 {
52            let i = self.rand(n as _) as usize;
53            n -= 1;
54            slice.swap(i, n);
55        }
56    }

More examples

Hide additional examples

crates/competitive/src/heuristic/simulated_annealing.rs (line 77)

69    pub fn is_accepted(&mut self, current_score: f64, next_score: f64) -> bool {
70        let diff = if self.is_maximize {
71            next_score - current_score
72        } else {
73            current_score - next_score
74        };
75        diff >= 0.
76            || diff
77                > self.log_table[self.rand.rand(Self::LOG_TABLE_SIZE as u64) as usize]
78                    * self.temperture
79    }
80    pub fn accepted_score(&mut self, current_score: f64) -> f64 {
81        let bound =
82            self.log_table[self.rand.rand(Self::LOG_TABLE_SIZE as u64) as usize] * self.temperture;
83        if self.is_maximize {
84            current_score + bound
85        } else {
86            current_score - bound
87        }
88    }

crates/competitive/src/tools/random_generator.rs (line 264)

257    fn rand(&self, rng: &mut Xorshift) -> (Bound<T>, Bound<T>) {
258        let mut l = rng.random(&self.data);
259        let mut r = rng.random(&self.data);
260        if l > r {
261            swap(&mut l, &mut r);
262        }
263        (
264            match rng.rand(3) {
265                0 => Bound::Excluded(l),
266                1 => Bound::Included(l),
267                _ => Bound::Unbounded,
268            },
269            match rng.rand(3) {
270                0 => Bound::Excluded(r),
271                1 => Bound::Included(r),
272                _ => Bound::Unbounded,
273            },
274        )
275    }
276}
277
278#[inline]
279fn randint_uniform(rng: &mut Xorshift, k: u64) -> u64 {
280    let mut v = rng.rand64();
281    if k > 0 {
282        v %= k;
283    }
284    v
285}
286
287pub struct WeightedSampler {
288    n: usize,
289    prob: Vec<f64>,
290    alias: Vec<usize>,
291}
292
293impl WeightedSampler {
294    pub fn new(weights: impl IntoIterator<Item = f64>) -> Self {
295        let mut weights: Vec<_> = weights.into_iter().collect();
296        let n = weights.len();
297        assert!(n > 0, "weights must be non-empty");
298        let mut prob = vec![0.0; n];
299        let mut alias = vec![0; n];
300        let mut small = vec![];
301        let mut large = vec![];
302        let sum: f64 = weights.iter().sum();
303        assert!(sum > 0.0, "sum of weights must be positive");
304        for (i, weight) in weights.iter_mut().enumerate() {
305            assert!(*weight >= 0.0, "weights must be non-negative");
306            *weight *= n as f64 / sum;
307            if *weight < 1.0 {
308                small.push(i);
309            } else {
310                large.push(i);
311            }
312        }
313        loop {
314            match (small.pop(), large.pop()) {
315                (Some(l), Some(g)) => {
316                    prob[l] = weights[l];
317                    alias[l] = g;
318                    weights[g] -= 1.0 - weights[l];
319                    if weights[g] < 1.0 {
320                        small.push(g);
321                    } else {
322                        large.push(g);
323                    }
324                }
325                (Some(g), None) | (None, Some(g)) => {
326                    prob[g] = 1.0;
327                    alias[g] = g;
328                }
329                (None, None) => break,
330            }
331        }
332        Self { n, prob, alias }
333    }
334}
335
336impl RandomSpec<usize> for WeightedSampler {
337    fn rand(&self, rng: &mut Xorshift) -> usize {
338        let i = rng.rand(self.n as u64) as usize;
339        if rng.randf() < self.prob[i] {
340            i
341        } else {
342            self.alias[i]
343        }
344    }

crates/competitive/src/tree/generator.rs (line 48)

43        fn rand_inner(n: usize, rng: &mut Xorshift) -> Vec<(usize, usize)> {
44            let mut edges = Vec::with_capacity(n.saturating_sub(1));
45            if n >= 2 {
46                let k = rng.random(1..n);
47                for n in [k, n - k].iter().cloned() {
48                    let ty = rng.rand(6);
49                    edges.extend(match ty {
50                        0 => from_prufer_sequence(
51                            n,
52                            &rng.random_iter(0..n)
53                                .take(n.saturating_sub(2))
54                                .collect::<Vec<usize>>(),
55                        ),
56                        1 => (1..n).map(|u| (u - 1, u)).collect(),
57                        2 => (1..n).map(|u| (0, u)).collect(),
58                        _ => rand_inner(n, rng),
59                    });
60                }
61                for (u, v) in edges[k - 1..].iter_mut() {
62                    *u += k;
63                    *v += k;
64                }
65                edges.push((rng.random(0..k), rng.random(k..n)));
66            }
67            edges
68        }

crates/competitive/src/math/discrete_logarithm.rs (line 204)

184fn index_calculus_for_primitive_root(
185    p: u64,
186    ord: u64,
187    br_primes: &[BarrettReduction<u64>],
188    prec: &QdrtPowPrec,
189) -> Vec<u64> {
190    let br_ord = BarrettReduction::<u128>::new(ord as u128);
191    let mul = |x: u64, y: u64| br_ord.rem(x as u128 * y as u128) as u64;
192    let sub = |x: u64, y: u64| if x < y { x + ord - y } else { x - y };
193
194    let pc = br_primes.len();
195    let mut mat: Vec<Vec<u64>> = vec![];
196    let mut rows: Vec<Vec<u64>> = vec![];
197
198    let mut rng = Xorshift::default();
199    let br = BarrettReduction::<u128>::new(p as u128);
200
201    for i in 0..pc {
202        for ri in 0usize.. {
203            let mut row = vec![0u64; pc + 1];
204            let mut kk = rng.rand(ord - 1) + 1;
205            let mut gkk = prec.pow(kk, &br);
206            let mut k = kk;
207            let mut gk = gkk;
208            while ri >= rows.len() {
209                row[pc] = k;
210                if factorize_smooth(gk, &mut row, br_primes) {
211                    rows.push(row);
212                    break;
213                }
214                if k + kk < ord {
215                    k += kk;
216                    gk = br.rem(gk as u128 * gkk as u128) as u64;
217                } else {
218                    kk = rng.rand(ord - 1) + 1;
219                    gkk = prec.pow(kk, &br);
220                    k = kk;
221                    gk = gkk;
222                }
223            }
224            let row = &mut rows[ri];
225            for j in 0..i {
226                if row[j] != 0 {
227                    let b = mul(modinv(mat[j][j], ord), row[j]);
228                    for (r, a) in row[j..].iter_mut().zip(&mat[j][j..]) {
229                        *r = sub(*r, mul(*a, b));
230                    }
231                }
232                assert_eq!(row[j], 0);
233            }
234            if gcd(row[i], ord) == 1 {
235                let last = rows.len() - 1;
236                rows.swap(ri, last);
237                mat.push(rows.pop().unwrap());
238                break;
239            }
240        }
241    }
242    for i in (0..pc).rev() {
243        for j in i + 1..pc {
244            mat[i][pc] = sub(mat[i][pc], mul(mat[i][j], mat[j][pc]));
245        }
246        mat[i][pc] = mul(mat[i][pc], modinv(mat[i][i], ord));
247    }
248    (0..pc).map(|i| mat[i][pc]).collect()
249}
250
251#[derive(Debug)]
252struct IndexCalculusWithPrimitiveRoot {
253    p: u64,
254    ord: u64,
255    prec: QdrtPowPrec,
256    coeff: Vec<u64>,
257}
258
259impl IndexCalculusWithPrimitiveRoot {
260    fn new(p: u64, br_primes: &[BarrettReduction<u64>]) -> Self {
261        let ord = p - 1;
262        let g = primitive_root(p);
263        let br = BarrettReduction::<u128>::new(p as u128);
264        let prec = QdrtPowPrec::new(g, ord, &br);
265        let coeff = index_calculus_for_primitive_root(p, ord, br_primes, &prec);
266        Self {
267            p,
268            ord,
269            prec,
270            coeff,
271        }
272    }
273    fn index_calculus(&self, a: u64, br_primes: &[BarrettReduction<u64>]) -> Option<u64> {
274        let p = self.p;
275        let ord = self.ord;
276        let br = BarrettReduction::<u128>::new(p as u128);
277        let a = br.rem(a as _) as u64;
278        if a == 1 {
279            return Some(0);
280        }
281        if p == 2 {
282            return None;
283        }
284
285        let mut rng = Xorshift::new();
286        let mut row = vec![0u64; br_primes.len()];
287        let mut kk = rng.rand(ord - 1) + 1;
288        let mut gkk = self.prec.pow(kk, &br);
289        let mut k = kk;
290        let mut gk = br.rem(gkk as u128 * a as u128) as u64;
291        loop {
292            if factorize_smooth(gk, &mut row, br_primes) {
293                let mut res = ord - k;
294                for (&c, &r) in self.coeff.iter().zip(&row) {
295                    for _ in 0..r {
296                        res += c;
297                        if res >= ord {
298                            res -= ord;
299                        }
300                    }
301                }
302                return Some(res);
303            }
304            if k + kk < ord {
305                k += kk;
306                gk = br.rem(gk as u128 * gkk as u128) as u64;
307            } else {
308                kk = rng.rand(ord - 1) + 1;
309                gkk = self.prec.pow(kk, &br);
310                k = kk;
311                gk = br.rem(gkk as u128 * a as u128) as u64;
312            }
313        }
314    }

crates/competitive/src/math/fast_prime_mod.rs (line 283)

227fn build_log<const P: u32>(root: u32, pow_lo: &[u32], pow_hi: &[u32]) -> Box<[u32]> {
228    let k = table_k::<P>();
229    let ord = P - 1;
230    let mut lpf = vec![0; k + 1].into_boxed_slice();
231    let mut primes = vec![];
232    lpf[1] = 1;
233    for i in 2..=k {
234        if lpf[i] == 0 {
235            lpf[i] = i as u32;
236            primes.push(i as u32);
237        }
238        for &p in primes.iter() {
239            let p = p as usize;
240            if p > lpf[i] as usize || p > k / i {
241                break;
242            }
243            lpf[i * p] = p as u32;
244        }
245    }
246
247    let baby_size = (BSGS_SIZE as u32).min(ord);
248    let mut baby = U32Map::new(baby_size as usize);
249    let mut pw = 1;
250    for i in 0..baby_size {
251        baby.insert(pw, i);
252        pw = mul_mod_raw::<P>(pw, root);
253    }
254    let q = pow_root_raw::<P>(ord - baby_size, pow_lo, pow_hi);
255
256    let mut log = vec![0; table_len::<P>()].into_boxed_slice();
257    log[k + 1] = 0;
258    let mut rng = Xorshift::default();
259    let small_primes = [2, 3, 5, 7, 11, 13, 17, 19];
260    for i in 2..=k {
261        let p = lpf[i] as usize;
262        if p < i {
263            log[k + i] = add_mod(log[k + p], log[k + i / p], ord);
264        } else if i < 100 {
265            let mut x = i as u32;
266            let mut ans = 0;
267            loop {
268                if let Some(v) = baby.get(x) {
269                    log[k + i] = ans + v;
270                    break;
271                }
272                ans += baby_size;
273                x = mul_mod_raw::<P>(x, q);
274            }
275        } else if i > P as usize / i {
276            let j = (P as usize) / i;
277            let r = (P as usize) % i;
278            let x = add_mod(log[k + r], ord / 2, ord);
279            let y = log[k + j];
280            log[k + i] = if x >= y { x - y } else { x + ord - y };
281        } else {
282            loop {
283                let exp = rng.rand(ord as u64) as u32;
284                let mut ans = if exp == 0 { 0 } else { ord - exp };
285                let mut x = mul_mod_raw::<P>(i as u32, pow_root_raw::<P>(exp, pow_lo, pow_hi));
286                for q in small_primes {
287                    while x.is_multiple_of(q) {
288                        x /= q;
289                        ans = add_mod(ans, log[k + q as usize], ord);
290                    }
291                }
292                if x as usize >= k {
293                    continue;
294                }
295                while (i as u32) < x && lpf[x as usize] < i as u32 {
296                    let q = lpf[x as usize];
297                    x /= q;
298                    ans = add_mod(ans, log[k + q as usize], ord);
299                }
300                if 1 < x && x < i as u32 {
301                    ans = add_mod(ans, log[k + x as usize], ord);
302                    x = 1;
303                }
304                if x == 1 {
305                    log[k + i] = ans;
306                    break;
307                }
308            }
309        }
310    }
311    for i in 1..=k {
312        log[k - i] = add_mod(log[k + i], ord / 2, ord);
313    }
314    log
315}

Source

pub fn rands(&mut self, k: u64, n: usize) -> Vec<u64>

Source

pub fn randf(&mut self) -> f64

Examples found in repository ?

crates/competitive/src/tools/xorshift.rs (line 46)

45    pub fn gen_bool(&mut self, p: f64) -> bool {
46        self.randf() < p
47    }

More examples

Hide additional examples

crates/competitive/src/tools/random_generator.rs (line 339)

337    fn rand(&self, rng: &mut Xorshift) -> usize {
338        let i = rng.rand(self.n as u64) as usize;
339        if rng.randf() < self.prob[i] {
340            i
341        } else {
342            self.alias[i]
343        }
344    }

crates/competitive/src/string/wildcard_pattern_matching.rs (line 13)

7fn wildcard_pattern_matching_with_rng(p: &[u8], s: &[u8], rng: &mut Xorshift) -> Vec<bool> {
8    assert!(!p.is_empty());
9    assert!(p.len() <= s.len());
10    let mut direct = [0.0; 256];
11    let mut inverse = [0.0; 256];
12    for i in 0..256 {
13        let x = 1.25 + 0.75 * rng.randf();
14        direct[i] = x;
15        inverse[i] = 1.0 / x;
16    }
17    direct[b'?' as usize] = 0.0;
18    inverse[b'?' as usize] = 0.0;
19    ConvolveRealFft::middle_product_f64(
20        s.iter().map(|&c| direct[c as usize]),
21        p.iter().rev().map(|&c| inverse[c as usize]),
22    )
23    .into_iter()
24    .map(|x| (x - x.round()).abs() < 1e-8)
25    .collect()
26}

Source

pub fn gen_bool(&mut self, p: f64) -> bool

Source

pub fn shuffle<T>(&mut self, slice: &mut [T])

Examples found in repository ?

crates/competitive/src/data_structure/submask_range_query.rs (line 21)

17    pub fn new(bit_width: u32) -> Self {
18        let mut rng = Xorshift::default();
19        let mut mask = [0; 3];
20        let mut rem: Vec<_> = (0..bit_width).map(|w| w % 3).collect();
21        rng.shuffle(&mut rem);
22        for (k, r) in rem.into_iter().enumerate() {
23            mask[r as usize] |= 1 << k;
24        }
25        Self { bit_width, mask }
26    }