結果
| 問題 |
No.1749 ラムドスウイルスの感染拡大
|
| コンテスト | |
| ユーザー |
 motoshira
|
| 提出日時 | 2021-11-21 20:30:21 |
| 言語 | Common Lisp (sbcl 2.5.0) |
| 結果 |
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 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 26 |
コンパイルメッセージ
; 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)))