Submission #5123059

---

Source Code Expand

(eval-when (:compile-toplevel :load-toplevel :execute)
  (defparameter OPT
    #+swank '(optimize (speed 3) (safety 2))
    #-swank '(optimize (speed 3) (safety 0) (debug 0)))
  #+swank (progn (ql:quickload '(:cl-debug-print :fiveam))
                 (shadow :run)
                 (use-package :fiveam)))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)

;; BEGIN_INSERTED_CONTENTS
(declaim ((simple-array double-float (*)) *bernoulli*))
(defparameter *bernoulli*
  #.(coerce
     (mapcar (lambda (x) (float x 1d0))
             '(1 -1/2 1/6 0 -1/30 0 1/42 0 -1/30 0 5/66 0 -691/2730 0 7/6 0 -3617/510 0 43867/798 0 -174611/330 0 854513/138 0 -236364091/2730 0 8553103/6 0 -23749461029/870 0 8615841276005/14332 0))
     '(simple-array double-float (*))))

(declaim ((simple-array (unsigned-byte 62) (*)) *factorial*))
(defparameter *factorial*
  (make-array 21 :element-type '(unsigned-byte 62) :initial-contents '(1 1 2 6 24 120 720 5040 40320 362880 3628800 39916800 479001600 6227020800 87178291200 1307674368000 20922789888000 355687428096000 6402373705728000 121645100408832000 2432902008176640000)))

(declaim (ftype (function * (values double-float &optional)) log-factorial))
(defun log-factorial (n &optional (terms 4))
  (declare #.OPT
           (uint62 n)
           ((unsigned-byte 8) terms))
  (if (<= n 20)
      (log (float (aref *factorial* n) 1d0))
      (let ((n (float n 1d0)))
        (+ #.(log (sqrt (* 2d0 pi)))
           (* (+ n 0.5d0) (log n))
           (- n)
           (loop for i2 from 2 to (* terms 2) by 2
                 sum (/ (aref *bernoulli* i2)
                        (* i2 (- i2 1) (expt n (- i2 1))))
                 of-type double-float)))))

(declaim (ftype (function * (values double-float &optional)) log-binomial))
(defun log-binomial (n k &optional (terms 4))
  (declare (uint62 n k))
  (assert (>= n k))
  (- (log-factorial n terms)
     (log-factorial (- n k) terms)
     (log-factorial k terms)))

(defmacro dbg (&rest forms)
  #+swank
  (if (= (length forms) 1)
      `(format *error-output* "~A => ~A~%" ',(car forms) ,(car forms))
      `(format *error-output* "~A => ~A~%" ',forms `(,,@forms)))
  #-swank (declare (ignore forms)))

(defmacro define-int-types (&rest bits)
  `(progn
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "UINT~A" b)) () '(unsigned-byte ,b))) bits)
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "INT~A" b)) () '(signed-byte ,b))) bits)))
(define-int-types 2 4 7 8 15 16 31 32 62 63 64)

(declaim (inline println))
(defun println (obj &optional (stream *standard-output*))
  (let ((*read-default-float-format* 'double-float))
    (prog1 (princ obj stream) (terpri stream))))

(defconstant +mod+ 1000000007)

;; Body

;; The probability that you go parallel to the x-axis k+ times by +D, k- times
;; by -D, to the y-axis l+ times by +D, l- times by -D.
(defun calc (k+ k- l+ l- n)
  (declare (uint32 k+ k- l+ l- n))
  (assert (= n (+ k+ k- l+ l-)))
  (exp (+ (log-binomial n k+ 3)
          (log-binomial (- n k+) k- 3)
          (log-binomial (- n k+ k-) l- 3)
          (- (* n (log 4))))))

(defun main ()
  (declare #.OPT)
  (let* ((n (read))
         (d (read))
         (x (read))
         (y (read)))
    (declare (int32 n d x y))
    (if (zerop (mod x d))
        (setf x (floor x d))
        (progn (println 0)
               (return-from main)))
    (if (zerop (mod y d))
        (setf y (floor y d))
        (progn (println 0)
               (return-from main)))
    (let ((res 0d0))
      (declare (double-float res))
      (loop for k+ from 0 to n
            for k- = (- k+ x)
            when (<= 0 k- n)
            do (when (evenp (- n k+ k- y))
                 (let ((l+ (floor (+ n (- k+) (- k-) y) 2))
                       (l- (floor (- n k+ k- y) 2)))
                   (when (and (<= 0 l+ n)
                              (<= 0 l- n))
                     (incf res (calc k+ k- l+ l- n))))))
      (println res))))

#-swank(main)

Submission Info

Judge Result