結果
| 問題 | No.1750 ラムドスウイルスの感染拡大-hard |
| ユーザー |
 motoshira
|
| 提出日時 | 2021-11-21 23:44:00 |
| 言語 | Common Lisp (sbcl 2.3.8) |
| 結果 |
AC
|
| 実行時間 | 551 ms / 2,000 ms |
| コード長 | 9,738 bytes |
| コンパイル時間 | 894 ms |
| コンパイル使用メモリ | 56,128 KB |
| 実行使用メモリ | 36,608 KB |
| 最終ジャッジ日時 | 2023-09-05 10:45:27 |
| 合計ジャッジ時間 | 9,750 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge12 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 8 ms
23,716 KB |
| testcase_01 | AC | 10 ms
27,684 KB |
| testcase_02 | AC | 9 ms
25,736 KB |
| testcase_03 | AC | 10 ms
27,708 KB |
| testcase_04 | AC | 57 ms
26,296 KB |
| testcase_05 | AC | 9 ms
27,672 KB |
| testcase_06 | AC | 9 ms
23,640 KB |
| testcase_07 | AC | 8 ms
23,636 KB |
| testcase_08 | AC | 389 ms
30,424 KB |
| testcase_09 | AC | 389 ms
30,532 KB |
| testcase_10 | AC | 387 ms
32,560 KB |
| testcase_11 | AC | 378 ms
30,388 KB |
| testcase_12 | AC | 395 ms
32,396 KB |
| testcase_13 | AC | 388 ms
30,464 KB |
| testcase_14 | AC | 505 ms
36,196 KB |
| testcase_15 | AC | 521 ms
32,436 KB |
| testcase_16 | AC | 522 ms
36,288 KB |
| testcase_17 | AC | 529 ms
34,512 KB |
| testcase_18 | AC | 551 ms
34,572 KB |
| testcase_19 | AC | 526 ms
34,508 KB |
| testcase_20 | AC | 367 ms
36,200 KB |
| testcase_21 | AC | 416 ms
34,544 KB |
| testcase_22 | AC | 78 ms
28,300 KB |
| testcase_23 | AC | 499 ms
36,608 KB |
| testcase_24 | AC | 63 ms
28,240 KB |
| testcase_25 | AC | 147 ms
33,936 KB |
| testcase_26 | AC | 50 ms
26,444 KB |
| testcase_27 | AC | 10 ms
23,776 KB |
| testcase_28 | AC | 11 ms
23,964 KB |
| testcase_29 | AC | 10 ms
29,840 KB |
| testcase_30 | AC | 78 ms
31,888 KB |
| testcase_31 | AC | 73 ms
28,260 KB |
| testcase_32 | AC | 73 ms
30,264 KB |
| testcase_33 | AC | 70 ms
28,256 KB |
コンパイルメッセージ
; compiling file "/home/judge/data/code/Main.lisp" (written 05 SEP 2023 10:45:16 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 (DEFCONSTANT +MOD+ ...) ; processing (DECLAIM (INLINE MAT*)) ; processing (DEFUN MAT* ...) ; processing (DEFUN MAIN ...) ; processing (MAIN) ; wrote /home/judge/data/code/Main.fasl ; compilation finished in 0:00:00.170
ソースコード
(in-package #:cl-user)
;;------------------------------Preferences------------------------------
(eval-when (:compile-toplevel :load-toplevel :execute)
(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
;;;
;;---------------------------------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))
(defconstant +mod+ 998244353)
(declaim (inline mat*))
(defun mat* (m1 m2 n)
(declare ((simple-array fixnum (* *)) m1 m2)
(fixnum n))
(let* ((res (make-array (list n n) :element-type 'fixnum)))
(declare ((simple-array fixnum (* *)) res))
(loop :for i :of-type fixnum :below n
:do (loop :for j :of-type fixnum :below n
:for tmp :of-type fixnum := 0
:do (loop :for k :of-type fixnum :below n
:do (setf (the fixnum tmp)
(rem (the fixnum
(+ tmp
(rem (the fixnum
(* (aref m1 i k)
(aref m2 k j)))
+mod+)))
+mod+)))
(setf (aref res i j) tmp)))
res))
(defun main ()
(let* ((n (read))
(m (read))
(time (read))
(es (read-into m 'vector (lambda () (list (read) (read)))))
(am (make-array (list n n) :element-type 'fixnum
:initial-element 0)))
(declare (fixnum n m time)
((simple-array fixnum (* *)) am))
(loop :for (a b) :across es
:do (setf (aref am a b) 1)
(setf (aref am b a) 1))
(let* ((dub (make-array 61)))
(declare ((simple-array t (*)) dub))
(setf (aref dub 0) am)
(dotimes (d 60)
(setf (aref dub (1+ d))
(mat* (aref dub d)
(aref dub d)
n)))
(let ((bm (make-array (list n n) :element-type 'fixnum
:initial-element 0))
(d 0)
(k time))
(declare ((simple-array fixnum (* *)) bm)
(fixnum d k))
(dotimes (i n)
(setf (aref bm i i) 1))
(loop :while (plusp k)
:do (psetf (the fixnum k) (the fixnum (ash k -1))
(the (simple-array fixnum (* *)) bm)
(if (oddp k)
(mat* (aref dub d)
bm
n)
bm)
(the fixnum d) (the fixnum (1+ d))))
(println (aref bm 0 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)))