Submission #6530475

---

Source Code Expand

;; -*- coding: utf-8 -*-
(eval-when (:compile-toplevel :load-toplevel :execute)
  (defparameter OPT
    #+swank '(optimize (speed 3) (safety 2))
    #-swank '(optimize (speed 3) (safety 0) (debug 0)))
  #+swank (ql:quickload '(:cl-debug-print :fiveam))
  #-swank (set-dispatch-macro-character #\# #\> (lambda (s c p) (declare (ignore c p)) (read s nil (values) t))))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)
#-swank (disable-debugger) ; for CS Academy

;; BEGIN_INSERTED_CONTENTS
(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
(defun main ()
  (declare #.OPT)
  (let* ((n (read))
         (k (read))
         (dp (make-array (+ 1 n) :element-type 'uint32)))
    (declare (uint31 n k))
    (setf (aref dp 0) 0
          (aref dp 1) 1)
    (loop for i from 2 to n
          do (setf (aref dp i)
                   (mod (cond ((< i k)
                               (* 2 (aref dp (- i 1))))
                              ((= i n)
                               (- (aref dp (- i 1))
                                  (if (= i k)
                                      1
                                      (aref dp (- i k 1)))))
                              ((= i k)
                               (- (* 2 (aref dp (- i 1))) 1))
                              (t
                               (- (* 2 (aref dp (- i 1)))
                                  (aref dp (- i k 1)))))
                        +mod+)))
    (println (aref dp n))))

#-swank (main)

Submission Info

Judge Result