haar_lib/math/
nim_product.rs

1//! Nimber product
2//!
3//! # Problems
4//! - <https://judge.yosupo.jp/problem/nim_product_64>
5
6const NIM_PRODUCT_TABLE_16: [[u8; 16]; 16] = [
7    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
8    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15],
9    [0, 2, 3, 1, 8, 10, 11, 9, 12, 14, 15, 13, 4, 6, 7, 5],
10    [0, 3, 1, 2, 12, 15, 13, 14, 4, 7, 5, 6, 8, 11, 9, 10],
11    [0, 4, 8, 12, 6, 2, 14, 10, 11, 15, 3, 7, 13, 9, 5, 1],
12    [0, 5, 10, 15, 2, 7, 8, 13, 3, 6, 9, 12, 1, 4, 11, 14],
13    [0, 6, 11, 13, 14, 8, 5, 3, 7, 1, 12, 10, 9, 15, 2, 4],
14    [0, 7, 9, 14, 10, 13, 3, 4, 15, 8, 6, 1, 5, 2, 12, 11],
15    [0, 8, 12, 4, 11, 3, 7, 15, 13, 5, 1, 9, 6, 14, 10, 2],
16    [0, 9, 14, 7, 15, 6, 1, 8, 5, 12, 11, 2, 10, 3, 4, 13],
17    [0, 10, 15, 5, 3, 9, 12, 6, 1, 11, 14, 4, 2, 8, 13, 7],
18    [0, 11, 13, 6, 7, 12, 10, 1, 9, 2, 4, 15, 14, 5, 3, 8],
19    [0, 12, 4, 8, 13, 1, 9, 5, 6, 10, 2, 14, 11, 7, 15, 3],
20    [0, 13, 6, 11, 9, 4, 15, 2, 14, 3, 8, 5, 7, 10, 1, 12],
21    [0, 14, 7, 9, 5, 11, 2, 12, 10, 4, 13, 3, 15, 1, 8, 6],
22    [0, 15, 5, 10, 1, 14, 4, 11, 2, 13, 7, 8, 3, 12, 6, 9],
23];
24
25thread_local! {
26    static NIM_PRODUCT_TABLE_256: [[u8; 256]; 256] = {
27        let mut ret = [[0; 256]; 256];
28
29        let mask: u8 = 0xf;
30
31        for a in 0..=255 {
32            for b in 0..=255 {
33                let au = (a >> 4) as usize;
34                let al = (a & mask) as usize;
35                let bu = (b >> 4) as usize;
36                let bl = (b & mask) as usize;
37
38                let au_bu = NIM_PRODUCT_TABLE_16[au][bu];
39                let al_bu = NIM_PRODUCT_TABLE_16[al][bu];
40                let au_bl = NIM_PRODUCT_TABLE_16[au][bl];
41                let al_bl = NIM_PRODUCT_TABLE_16[al][bl];
42
43                ret[a as usize][b as usize] = ((au_bu ^ al_bu ^ au_bl) << 4)
44                    ^ NIM_PRODUCT_TABLE_16[au][NIM_PRODUCT_TABLE_16[bu][1 << 3] as usize]
45                    ^ al_bl;
46            }
47        }
48
49        ret
50    };
51}
52
53/// [`u8`]同士のNimber productを求める。
54pub fn nim_product_8(a: u8, b: u8) -> u8 {
55    NIM_PRODUCT_TABLE_256.with(|t| t[a as usize][b as usize])
56}
57
58macro_rules! impl_nim_product {
59    ( $(#[$meta:meta])* $uint:ty, $np:ident, $uint_h:ty, $np_h:ident, $bits:expr ) => {
60        $(#[$meta])*
61        pub fn $np(a: $uint, b: $uint) -> $uint {
62            let bits = $bits;
63
64            let mask = (1 << bits) - 1;
65
66            let au = (a >> bits) as $uint_h;
67            let al = (a & mask) as $uint_h;
68            let bu = (b >> bits) as $uint_h;
69            let bl = (b & mask) as $uint_h;
70
71            let au_bu = $np_h(au, bu) as $uint;
72            let al_bu = $np_h(al, bu) as $uint;
73            let au_bl = $np_h(au, bl) as $uint;
74            let al_bl = $np_h(al, bl) as $uint;
75
76            ((au_bu ^ al_bu ^ au_bl) << bits)
77                ^ $np_h(au, $np_h(bu, 1 << (bits - 1))) as $uint
78                ^ al_bl
79        }
80    };
81}
82
83impl_nim_product!(
84    /// [`u64`]同士のNimber productを求める。
85    u64, nim_product_64, u32, nim_product_32, 32
86);
87impl_nim_product!(
88    /// [`u32`]同士のNimber productを求める。
89    u32, nim_product_32, u16, nim_product_16, 16
90);
91impl_nim_product!(
92    /// [`u16`]同士のNimber productを求める。
93    u16, nim_product_16, u8, nim_product_8, 8
94);
95
96#[cfg(test)]
97mod tests {
98    use super::*;
99
100    #[test]
101    fn test() {
102        assert_eq!(
103            nim_product_64(18446744073709551615, 18446744073709551615),
104            11290409524105353207
105        );
106    }
107}
haar_lib/math/nim_product.rs

haar_lib/math/
nim_product.rs
