对 $2^{61}-1$ 快速取模的实现存档。 1 2 3 4 5 6 7 8 9 10 11 template <typename T> constexpr uint64_t mod(T res) { constexpr uint64_t mod_p = (1ull << 61) - 1; res = (res >> 61) + (res & mod_p); res = (res >> 61) + (res & mod_p); if (res == mod_p) { return 0; } return res; }
splitmix64 的实现存档。 1 2 3 4 5 6 7 8 9 10 #include <cstdint> uint64_t splitmix64(uint64_t x) { // 固定的“魔法”常数，都是精心挑选的 x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; x = x ^ (x >> 31); return x; }
一个自动的 24 点求解器。输入四个数字就会自动输出所有解。 目前还有一点局限性：它会输出许多本质相同的解，比如 a 和 -(-a)。所以下一步可以实现表达式正则化和去重。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 #lang racket (define a (make-vector 4)) (let read-a ([i 0]) (when (< i 4) (vector-set! a i (read)) (when (not (number? (vector-ref a i))) (error "Invalid input!")) (read-a (+ i 1))) (vector-sort! a <)) (struct node (val op1 op2 e1 e2) #:transparent #:mutable) (define (print-ans p) (if (eq? (node-e1 p) (void)) (display (node-val p)) (begin (display #\() ; (display #\() (when (eq? (node-op1 p) '-) (display (node-op1 p))) (print-ans (node-e1 p)) (display (node-op2 p)) ; (display #\() (print-ans (node-e2 p)) ; (display #\)) (display #\))))) (define operators (list (cons '+ +) (cons '- -) (cons '* *) (cons '/ /))) (define (solve l r) (if (= l r) (list (node (vector-ref a l) (void) (void) (void) (void))) (let ([res '()]) (let loop ([i l]) (when (< i r) (let ([p1 (solve l i)] [p2 (solve (+ i 1) r)]) (for* ([op1 operators] [op2 operators] [e1 p1] [e2 p2]) (unless (or (and (= (node-val e2) 0) (eq? (car op2) '/)) (eq? (car op1) '*) (eq? (car op1) '/)) (let ([val ((cdr op2) ((cdr op1) (node-val e1)) (node-val e2))]) (set! res (cons (node val (car op1) (car op2) e1 e2) res)))))) (loop (+ i 1)))) res))) (define ans (void)) ; Helper function to reverse a subarray of vector `v` from `start` to `end` inclusive. (define (reverse-subarray v start end) (let loop ([i start] [j end]) (when (< i j) ; Swap elements at index i and j (let ([temp (vector-ref v i)]) (vector-set! v i (vector-ref v j)) (vector-set! v j temp)) (loop (+ i 1) (- j 1))))) ; Implements the C++ std::next_permutation algorithm. ; Mutates global vector 'a' in place to the next lexicographical permutation. ; Returns #t if a next permutation was found, #f if it wrapped around to the first permutation. (define (next-permutation a) (let ([n (vector-length a)]) ; Step 1: Find pivot point 'i' (find first element a[i] < a[i+1] from right) (let loop-find-pivot ([i (- n 2)]) (cond ; Case 1: No pivot found (vector is in reverse order) [(< i 0) ; Reverse the whole vector to get the first permutation. (reverse-subarray a 0 (- n 1)) ; (displayln "!!!!!!!\n") #f] ; Return #f to indicate we wrapped around. ; Case 2: Found pivot point 'i' [(< (vector-ref a i) (vector-ref a (+ i 1))) ; (displayln i) ; Step 2: Find swap element 'j' (find first element a[j] > a[i] from right) (let loop-find-swap ([j (- n 1)]) (if (> (vector-ref a j) (vector-ref a i)) ; Step 3: Swap elements at i and j (let ([temp (vector-ref a i)]) (vector-set! a i (vector-ref a j)) (vector-set! a j temp)) (loop-find-swap (- j 1)))) ; Step 4: Reverse suffix starting from i + 1 (reverse-subarray a (+ i 1) (- n 1)) #t] ; Return #t to indicate a next permutation was found. ; Case 3: Continue searching for pivot point 'i' to the left [else (loop-find-pivot (- i 1))])))) (define (print-a) (let loop ([i 0]) (when (< i 4) (display (vector-ref a i)) (display #\space) (loop (+ i 1)))) (newline)) (let loop ([i 0]) (when (< i 24) ; (print-a) (set! ans (solve 0 3)) (for ([p ans]) (when (= (node-val p) 24) (print-ans p) (newline) #; (exit))) (when (next-permutation a) (loop (+ i 1)))))