結果
| 問題 | No.1749 ラムドスウイルスの感染拡大 |
| ユーザー |
 motoshira
|
| 提出日時 | 2021-11-21 20:30:21 |
| 言語 | Common Lisp (sbcl 2.3.8) |
| 結果 |
AC
|
| 実行時間 | 50 ms / 2,000 ms |
| コード長 | 9,183 bytes |
| コンパイル時間 | 1,122 ms |
| コンパイル使用メモリ | 55,040 KB |
| 実行使用メモリ | 35,928 KB |
| 最終ジャッジ日時 | 2023-09-05 06:26:43 |
| 合計ジャッジ時間 | 3,063 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge11 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 9 ms
23,572 KB |
| testcase_01 | AC | 10 ms
23,552 KB |
| testcase_02 | AC | 9 ms
23,532 KB |
| testcase_03 | AC | 10 ms
25,576 KB |
| testcase_04 | AC | 50 ms
26,032 KB |
| testcase_05 | AC | 10 ms
23,660 KB |
| testcase_06 | AC | 10 ms
23,648 KB |
| testcase_07 | AC | 10 ms
23,588 KB |
| testcase_08 | AC | 10 ms
23,700 KB |
| testcase_09 | AC | 9 ms
23,532 KB |
| testcase_10 | AC | 11 ms
32,192 KB |
| testcase_11 | AC | 12 ms
35,928 KB |
| testcase_12 | AC | 42 ms
32,560 KB |
| testcase_13 | AC | 11 ms
27,788 KB |
| testcase_14 | AC | 13 ms
23,832 KB |
| testcase_15 | AC | 20 ms
25,892 KB |
| testcase_16 | AC | 26 ms
23,968 KB |
| testcase_17 | AC | 46 ms
26,408 KB |
| testcase_18 | AC | 47 ms
34,588 KB |
| testcase_19 | AC | 35 ms
30,384 KB |
| testcase_20 | AC | 11 ms
23,880 KB |
| testcase_21 | AC | 10 ms
23,944 KB |
| testcase_22 | AC | 9 ms
23,596 KB |
| testcase_23 | AC | 9 ms
23,644 KB |
| testcase_24 | AC | 10 ms
25,608 KB |
| testcase_25 | AC | 13 ms
30,584 KB |
| testcase_26 | AC | 11 ms
26,424 KB |
| testcase_27 | AC | 12 ms
29,988 KB |
| testcase_28 | AC | 50 ms
26,096 KB |
| testcase_29 | AC | 47 ms
23,980 KB |
コンパイルメッセージ
; compiling file "/home/judge/data/code/Main.lisp" (written 05 SEP 2023 06:26:39 AM): ; processing (IN-PACKAGE #:CL-USER) ; processing (DECLAIM (OPTIMIZE # ...)) ; processing (DECLAIM (MUFFLE-CONDITIONS COMPILER-NOTE)) ; processing (DISABLE-DEBUGGER) ; processing (PUSHNEW :INLINE-GENERIC-FUNCION ...) ; processing (DEFPACKAGE #:MODINT ...) ; processing (IN-PACKAGE #:MODINT) ; processing (DECLAIM (FIXNUM *MOD*)) ; processing (DEFVAR *MOD* ...) ; processing (DECLAIM (INLINE MODINT) ...) ; processing (DEFUN MODINT ...) ; processing (DEFUN %OPERATE ...) ; processing (DEFUN + ...) ; processing (DEFUN - ...) ; processing (DEFUN * ...) ; processing (DEFUN / ...) ; processing (DEFMACRO %EXPAND ...) ; processing (DEFINE-COMPILER-MACRO + ...) ; processing (DEFINE-COMPILER-MACRO - ...) ; processing (DEFINE-COMPILER-MACRO * ...) ; processing (DEFINE-COMPILER-MACRO / ...) ; processing (DECLAIM (FTYPE # ...)) ; processing (DEFUN MOD-INV ...) ; processing (DECLAIM (FTYPE # ...) ...) ; processing (DEFUN MOD-POWER ...) ; processing (DEFINE-MODIFY-MACRO INCMODF ...) ; processing (DEFINE-MODIFY-MACRO DECMODF ...) ; processing (DEFINE-MODIFY-MACRO MULMODF ...) ; processing (DEFINE-MODIFY-MACRO DIVMODF ...) ; processing (DECLAIM (FTYPE # ...) ...) ; processing (DEFUN MAKE-MOD-FACT-TABLE ...) ; processing (DECLAIM (FTYPE # ...) ...) ; processing (DEFUN MOD-COMBI-WITH-TABLE ...) ; processing (IN-PACKAGE #:CL-USER) ; processing (DECLAIM (INLINE PRINTLN)) ; processing (DEFUN PRINTLN ...) ; processing (DEFUN READ-INTO ...) ; processing (DEFMACRO WITH-GENSYMS ...) ; processing (DEFMACRO DO-BFS ...) ; processing (DEFCONSTANT +INF+ ...) ; processing (DEFUN MAIN ...) ; processing (MAIN) ; wrote /home/judge/data/code/Main.fasl ; compilation finished in 0:00:00.114
ソースコード
(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)))