#718891 (Common Lisp) No.1749 ラムドスウイルスの感染拡大

• 問題: No.1749 ラムドスウイルスの感染拡大
• ユーザー: motoshira
• 提出日時: 2021-11-21 20:30:21
• 言語: Common Lisp (sbcl 2.3.8)
• 結果: AC
• 実行時間: 47 ms / 2,000 ms
• コード長: 9,183 bytes
• コンパイル時間: 1,381 ms
• コンパイル使用メモリ: 57,784 KB
• 実行使用メモリ: 30,848 KB
• 最終ジャッジ日時: 2024-06-23 02:48:13
• 合計ジャッジ時間: 2,772 ms
• ジャッジサーバーID （参考情報）: judge3 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	9 ms; 22,656 KB
testcase_01	AC	10 ms; 22,784 KB
testcase_02	AC	9 ms; 22,784 KB
testcase_03	AC	9 ms; 22,784 KB
testcase_04	AC	43 ms; 23,296 KB
testcase_05	AC	9 ms; 22,656 KB
testcase_06	AC	9 ms; 22,656 KB
testcase_07	AC	9 ms; 22,784 KB
testcase_08	AC	10 ms; 22,656 KB
testcase_09	AC	10 ms; 22,784 KB
testcase_10	AC	13 ms; 26,880 KB
testcase_11	AC	12 ms; 26,752 KB
testcase_12	AC	43 ms; 30,848 KB
testcase_13	AC	9 ms; 22,656 KB
testcase_14	AC	11 ms; 23,040 KB
testcase_15	AC	17 ms; 23,040 KB
testcase_16	AC	23 ms; 23,168 KB
testcase_17	AC	41 ms; 25,216 KB
testcase_18	AC	47 ms; 30,080 KB
testcase_19	AC	33 ms; 28,544 KB
testcase_20	AC	10 ms; 23,296 KB
testcase_21	AC	10 ms; 23,168 KB
testcase_22	AC	9 ms; 22,784 KB
testcase_23	AC	9 ms; 22,784 KB
testcase_24	AC	9 ms; 22,784 KB
testcase_25	AC	18 ms; 28,416 KB
testcase_26	AC	12 ms; 24,832 KB
testcase_27	AC	11 ms; 23,936 KB
testcase_28	AC	43 ms; 23,296 KB
testcase_29	AC	42 ms; 23,296 KB

コンパイルメッセージ

; compiling file "/home/judge/data/code/Main.lisp" (written 23 JUN 2024 02:48:10 AM):

; wrote /home/judge/data/code/Main.fasl
; compilation finished in 0:00:00.123

ソースコード

(in-package #:cl-user)

;;------------------------------Preferences------------------------------

(eval-when (:compile-toplevel :load-toplevel :execute)
  #+swank (declaim (optimize (speed 3) (safety 2)))
  #-swank (declaim (optimize (speed 3) (safety 0) (debug 0)))
  #+swank (load "~/ghq/github.com/motoshira/atcoder-submission/ac-tools/act.lisp")
  #+swank (ql:quickload :prove)
  #-swank (declaim (sb-ext:muffle-conditions sb-ext:compiler-note))
  #-swank (sb-ext:disable-debugger)
  (pushnew :inline-generic-funcion *features*))

;;;
;;; Beginning of inserted contents
;;;

;; modint functions

(defpackage #:modint
  (:use #:cl)
  (:nicknames #:m #:mod)
  (:shadow #:+
           #:-
           #:*
           #:/)
  (:export #:*mod*
           #:modint
           #:+
           #:-
           #:*
           #:/
           #:mod-inv
           #:mod-power
           #:make-mod-fact-table
           #:mod-combi-with-table
           #:incmodf
           #:decmodf
           #:mulmodf
           #:divmodf))

(in-package #:modint)

(declaim (fixnum *mod*))
(defvar *mod* 1000000007)

(declaim (inline modint)
         (ftype (function (integer) fixnum) modint))
(defun modint (integer)
  ;; (integer) -> (fixnum)
  ;; TODO TLE on big negative integer
  (declare (integer integer))
  (loop while (minusp integer)
        do (incf integer *mod*))
  (the fixnum
       (if (< integer *mod*)
           integer
           (mod integer *mod*))))

(defun %operate (fn args)
  (declare ((function (fixnum fixnum) fixnum) fn))
  (if (null args)
      0
      (reduce (lambda (x y)
                (modint (funcall fn x (modint y))))
              (rest args)
              :initial-value (first args))))

(defun + (&rest args)
  (%operate (lambda (x y)
              (cl:+ x y))
            args))

(defun - (&rest args)
  (%operate (lambda (x y)
              (cl:- x y))
            args))

(defun * (&rest args)
  (%operate (lambda (x y)
              (cl:* x y))
            args))

(defun / (&rest args)
  (%operate (lambda (x y)
              (cl:* x (mod-inv y)))
            args))

;; TODO compiler-macro

(defmacro %expand (fn x y)
  `(modint (funcall (the (function (fixnum fixnum) fixnum)
                         ,fn)
                    ,x
                    (modint ,y))))

(define-compiler-macro m:+ (&whole form &rest args)
  (if (> (length args) 10)
      form
      (reduce (lambda (acc x)
                `(%expand (lambda (x y)
                            (declare (fixnum x y))
                            (cl:+ x y))
                          ,acc
                          ,x))
              (rest args)
              :initial-value `(modint ,(first args)))))

(define-compiler-macro m:- (&whole form &rest args)
  (if (> (length args) 10)
      form
      (reduce (lambda (acc x)
                `(%expand (lambda (x y)
                            (declare (fixnum x y))
                            (cl:- x y))
                          ,acc
                          ,x))
              (rest args)
              :initial-value `(modint ,(first args)))))

(define-compiler-macro m:* (&whole form &rest args)
  (if (> (length args) 10)
      form
      (reduce (lambda (acc x)
                `(%expand (lambda (x y)
                            (declare (fixnum x y))
                            (cl:* x y))
                          ,acc
                          ,x))
              (rest args)
              :initial-value `(modint ,(first args)))))

(define-compiler-macro m:/ (&whole form &rest args)
  (if (> (length args) 10)
      form
      (reduce (lambda (acc x)
                `(%expand (lambda (x y)
                            (declare (fixnum x y))
                            (cl:* x (mod-inv y)))
                          ,acc
                          ,x))
              (rest args)
              :initial-value `(modint ,(first args)))))

(declaim (ftype (function (fixnum) fixnum) mod-inv))
(defun mod-inv (a)
  "Reference:https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a"
  (declare (fixnum a))
  (let ((b *mod*)
        (u 1)
        (v 0))
    (declare (fixnum b u v))
    (loop until (zerop b) do
      (let ((w (truncate a b)))
        (decf (the fixnum a) (the fixnum
                                  (cl:* (the fixnum w)
                                        (the fixnum b))))
        (rotatef (the fixnum a)
                 (the fixnum b))
        (decf (the fixnum u)
              (the fixnum
                   (cl:* (the fixnum w)
                         (the fixnum v))))
        (rotatef u v)))
    (modint u)))

(declaim (ftype (function (fixnum (integer 0)) fixnum) mod-power)
         (inline mod-power))
(defun mod-power (base power)
  ;; Reference:https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a
  (declare (fixnum base)
           ((integer 0) power))
  (loop while (plusp power)
        with res of-type fixnum = 1
        do (psetq base (the fixnum (* base base))
                  power (the (integer 0) (ash power -1))
                  res (the fixnum (if (logbitp 0 power)
                                    (* res base)
                                    res)))
        finally (return res)))

(define-modify-macro incmodf (&optional (val 1)) (lambda (place val) (+ place val)))
(define-modify-macro decmodf (&optional (val 1)) (lambda (place val) (- place val)))
(define-modify-macro mulmodf (&optional (val 1)) (lambda (place val) (* place val)))
(define-modify-macro divmodf (&optional (val 1)) (lambda (place val) (/ place val)))

(declaim (ftype (function (fixnum) (simple-array fixnum 1)) make-mod-table)
         (inline make-mod-fact-table))
(defun make-mod-fact-table (size)
  (declare (fixnum size))
  (let ((table (make-array (1+ size)
                           :element-type 'fixnum)))
    (declare ((simple-array fixnum 1) table))
    (setf (aref table 0) 1)
    (loop for i of-type fixnum below size
          do (setf (aref table (1+ i))
                   (* (aref table i)
                      (the fixnum (1+ i)))))
    table))

(declaim (ftype (function (fixnum fixnum (simple-array fixnum 1)) fixnum) mod-combi-with-table)
         (inline mod-combi-with-table))
(defun mod-combi-with-table (n k table)
  (declare (fixnum n k)
           ((simple-array fixnum 1) table))
  (the fixnum
       (if (or (< n k)
               (< n 0)
               (< k 0))
           0
           (/ (aref table n)
              (aref table k)
              (aref table (the fixnum (cl:- n k)))))))


;;;
;;; End of inserted contents
;;;

#+swank (load (merge-pathnames "test/modint.lisp" (uiop:current-lisp-file-pathname)) :if-does-not-exist nil)


;;---------------------------------Body---------------------------------

(in-package #:cl-user)

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

(defun read-into (count &optional (result-type 'list) (reader #'read))
  (coerce (loop :repeat count :collect (funcall reader)) result-type))

(defmacro with-gensyms ((&rest args) &body body)
  `(let ,(mapcar (lambda (arg) `(,arg (gensym))) args)
     ,@body))

(defmacro do-bfs ((&rest args) &body body)
  (with-gensyms (front tail empty-p pop!)
    (let ((vars (mapcar #'first args))
          (inits (mapcar #'second args))
          (types (mapcar #'third args)))
      `(let ((,front nil)
             (,tail nil))
         (declare (list ,front ,tail))
         (labels ((call (&rest args)
                    (push args ,tail))
                  (,empty-p ()
                    (and (null ,front)
                         (null ,tail)))
                  (,pop! ()
                    (when (null ,front)
                      (setf ,front (nreverse ,tail)
                            ,tail nil))
                    (pop ,front)))
           (declare (inline call ,empty-p ,pop!))
           (call ,@inits)
           (loop until (,empty-p)
                 for ,vars
                   of-type ,(or types (loop repeat (length args) collect t)) = (,pop!)
                 do ,@body))))))

(defconstant +inf+ #.(ash 1 60))

(defun main ()
  (let* ((m:*mod* 998244353)
         (n (read))
         (m (read))
         (time (read))
         (es (make-array m :initial-element nil)))
    (dotimes (i m)
      (let ((a (read))
            (b (read)))
        (setf (aref es i) (list a b))))
    (let ((dp (make-array n :initial-element 0)))
      (setf (aref dp 0) 1)
      (dotimes (tt time)
        (let ((next (make-array n :initial-element 0)))
          (loop :for (a b) :across es
                :do (m:incmodf (aref next b)
                        (aref dp a))
                    (m:incmodf (aref next a)
                        (aref dp b)))
          (setf dp next)))
      (println (aref dp 0)))))

#-swank (main)

#+swank
(defun run ()
  (let ((*standard-input*
          (make-string-input-stream
           (with-output-to-string (*standard-output*)
             (run-program
              (merge-pathnames "copy-or-paste" (truename "~/bin/"))
              '()
              :output *standard-output*)))))
    (main)))