結果
| 問題 |
No.1750 ラムドスウイルスの感染拡大-hard
|
| コンテスト | |
| ユーザー |
 motoshira
|
| 提出日時 | 2021-11-21 23:59:17 |
| 言語 | Common Lisp (sbcl 2.5.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 9,370 bytes |
| コンパイル時間 | 1,402 ms |
| コンパイル使用メモリ | 54,336 KB |
| 実行使用メモリ | 38,216 KB |
| 最終ジャッジ日時 | 2024-06-23 06:46:47 |
| 合計ジャッジ時間 | 4,894 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 4 TLE * 1 -- * 25 |
コンパイルメッセージ
; compiling file "/home/judge/data/code/Main.lisp" (written 23 JUN 2024 06:46:41 AM): ; wrote /home/judge/data/code/Main.fasl ; compilation finished in 0:00:00.093
ソースコード
(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 (fixnum) fixnum) modint))
(defun modint (integer)
;; (integer) -> (fixnum)
;; TODO TLE on big negative integer
(declare (fixnum integer))
(the fixnum
(rem 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))
(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))
(declare (fixnum n))
(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 (m:incmodf (the fixnum tmp)
(the fixnum
(m:* (aref m1 i k)
(aref m2 k j)))))
(setf (aref res i j) tmp)))
res))
(defun main ()
(let* ((m:*mod* 998244353)
(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 m:*mod* 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)))