Submission #4712556

---

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
(defmacro dbg (&rest forms)
  #+swank
  `(progn
     ,@(mapcar (lambda (form) `(format *error-output* "~A => ~A~%" ',form ,form))
               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)

(defmacro println (obj &optional (stream '*standard-output*))
  `(let ((*read-default-float-format* 'double-float))
     (prog1 (princ ,obj ,stream) (terpri ,stream))))

(defconstant +mod+ 1000000007)

;; Body
(defun make-com-table (size)
  (let* ((table (make-array (list size size)
                            :element-type 'double-float
                            :initial-element 0d0)))
    (setf (aref table 0 0) 1d0)
    (loop for i from 1 below size
          do (setf (aref table i 0) 1d0)
             (loop for j from 1 below size
                   do (setf (aref table i j)
                            (+ (aref table (- i 1) (- j 1))
                               (aref table (- i 1) j)))))
    table))

(declaim ((simple-array double-float (* *)) *com*))
(defparameter *com* (make-com-table 100))

(declaim (inline binom))
(defun binom (x y)
  (if (< x y)
      0
      (aref *com* x y)))

(defparameter *fact*
  (let ((table (make-array 101 :element-type 'double-float :initial-element 1d0)))
    (loop for i from 1 below (length table)
          do (setf (aref table i) (* i (aref table (- i 1)))))
    table))

(defun calc-expectation (d n)
  (declare (uint7 d n))
  (if (zerop d)
      1d0
      (/ (* (loop for p from 1 to n
                  sum (loop for prev-num from 0 to d by 2
                            sum (* (binom (- p 1) prev-num)
                                   (binom (- n p) (- d prev-num)))))
            (aref *fact* d))
         (/ (aref *fact* n)
            (aref *fact* (- n d 1))))))

(defun main ()
  (let* ((n (read))
         (cs (make-array n :element-type 'uint31))
         (ds (make-array n :element-type 'uint7)))
    (dotimes (i n) (setf (aref cs i) (read)))
    (dotimes (i n)
      (dotimes (j n)
        (when (and (not (= i j))
                   (zerop (mod (aref cs i) (aref cs j))))
          (incf (aref ds i)))))
    (println (loop for d across ds
                   sum (calc-expectation d n)))))

#-swank(main)

Submission Info

Judge Result