結果
| 問題 | No.1750 ラムドスウイルスの感染拡大-hard |
| ユーザー |
 motoshira
|
| 提出日時 | 2021-11-21 20:55:17 |
| 言語 | Common Lisp (sbcl 2.3.8) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 11,404 bytes |
| コンパイル時間 | 801 ms |
| コンパイル使用メモリ | 49,180 KB |
| 実行使用メモリ | 89,540 KB |
| 最終ジャッジ日時 | 2023-09-05 07:02:02 |
| 合計ジャッジ時間 | 12,423 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge11 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | RE | - |
| testcase_01 | RE | - |
| testcase_02 | RE | - |
| testcase_03 | RE | - |
| testcase_04 | RE | - |
| testcase_05 | RE | - |
| testcase_06 | RE | - |
| testcase_07 | RE | - |
| testcase_08 | RE | - |
| testcase_09 | RE | - |
| testcase_10 | RE | - |
| testcase_11 | RE | - |
| testcase_12 | RE | - |
| testcase_13 | RE | - |
| testcase_14 | TLE | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
コンパイルメッセージ
; compiling file "/home/judge/data/code/Main.lisp" (written 05 SEP 2023 07:01:48 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 (FTYPE # ...)) ; processing (DEFUN COPY-MATRIX ...) ; processing (DECLAIM (FTYPE # ...)) ; processing (DEFUN ROTATE-MATRIX ...) ; processing (DECLAIM (FTYPE # ...)) ; processing (DEFUN ROTATE-MATRIX! ...) ; processing (DECLAIM (FTYPE # ...)) ; processing (DEFUN MAT* ...) ; processing (DECLAIM (FTYPE # ...)) ; processing (DEFUN MAT-POW ...) ; processing (DECLAIM (INLINE PRINTLN)) ; processing (DEFUN PRINTLN ...) ; processing (DEFUN READ-INTO ...) ; processing (DEFUN MAIN ...) ; file: /home/judge/data/code/Main.lisp ; in: DEFUN MAIN ; (MAT* ; (LET ((T
ソースコード
(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
;;;
;;---------------------------------Body---------------------------------
(in-package #:cl-user)
(declaim (ftype (function ((array * 2)) (array * 2)) copy-matrix))
(defun copy-matrix (matrix)
(let ((new-mat (make-array (array-dimensions matrix)
:element-type (array-element-type matrix)
:adjustable (adjustable-array-p matrix))))
(loop for i of-type fixnum below (array-dimension matrix 0)
do (loop for j of-type fixnum below (array-dimension matrix 1)
do (setf (aref new-mat i j)
(aref matrix i j))))
new-mat))
(declaim (ftype (function ((array * 2)) (array * 2)) rotate-matrix))
(defun rotate-matrix (matrix)
" Return a matrix two-dimensional array rotated 90 degrees."
(let ((m (array-dimension matrix 0))
(n (array-dimension matrix 1)))
(let ((new-mat (make-array (list n m)
:element-type (array-element-type matrix)
:adjustable (adjustable-array-p matrix))))
(loop for i of-type fixnum below m
do (loop for j of-type fixnum below n
do (setf (aref new-mat j (- m i 1))
(aref matrix i j))))
new-mat)))
(declaim (ftype (function ((array * 2)) null) rotate-matrix!))
(defun rotate-matrix! (matrix)
" Destructively rotate MATRIX."
(destructuring-bind (m n) (array-dimensions matrix)
(loop for i of-type fixnum below n
do (loop for j of-type fixnum below m
do (rotatef (aref matrix j (- n i 1))
(aref matrix i j))))))
(declaim (ftype (function ((array * 2) (array * 2) &optional fixnum) (array * 2)) mat*))
(defun mat* (mat1 mat2 &optional modulo)
(destructuring-bind (m n) (array-dimensions mat1)
(destructuring-bind (p q) (array-dimensions mat2)
(assert (= n p))
(let ((new-mat (make-array (list m q)
:element-type (array-element-type mat1)
:adjustable (adjustable-array-p mat1))))
(loop for i of-type fixnum below m
do (loop for j of-type fixnum below q
do (setf (aref new-mat i j)
(loop for k of-type fixnum below n
sum (if modulo
(mod (* (aref mat1 i k)
(aref mat2 k j))
modulo)
(* (aref mat1 i k)
(aref mat2 k j)))))))
new-mat))))
(declaim (ftype (function ((array * 2) * &optional fixnum) (array * 2)) mat-pow))
(defun mat-pow (mat k &optional modulo)
(destructuring-bind (m n) (array-dimensions mat)
(assert (= m n))
(let ((res (make-array (list m n)
:element-type (array-element-type mat)
:adjustable (adjustable-array-p mat)
:initial-element 0)))
(loop for i of-type fixnum below n
do (setf (aref res i i) 1))
(sb-int:named-let rec ((k k)
(mat mat)
(res res))
(cond ((<= k 0) res)
((oddp k) (rec (ash k -1)
(mat* mat mat modulo)
(mat* mat res modulo)))
(t (rec (ash k -1)
(mat* mat mat modulo)
res)))))))
(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))
(defun main ()
(let* ((n (read))
(m (read))
(time (read))
(es (read-into m 'vector (lambda () (list (read) (read)))))
(am (make-array (list n n))))
(loop :for (a b) :across es
:do (setf (aref am a b) 1)
(setf (aref am b a) 1))
(let* ((pow (mat-pow am time 998244353))
(res (mat* (let ((tmp (make-array (list n n))))
(setf (aref tmp 0 0) 1)
tmp
998244353)
pow)))
(println (aref res 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)))