結果
問題 | No.891 隣接3項間の漸化式 |
ユーザー | sansaqua |
提出日時 | 2019-09-21 15:16:23 |
言語 | Common Lisp (sbcl 2.3.8) |
結果 |
AC
|
実行時間 | 12 ms / 2,000 ms |
コード長 | 9,930 bytes |
コンパイル時間 | 1,750 ms |
コンパイル使用メモリ | 89,200 KB |
実行使用メモリ | 30,912 KB |
最終ジャッジ日時 | 2024-09-18 23:24:34 |
合計ジャッジ時間 | 3,469 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 12 ms
30,908 KB |
testcase_01 | AC | 10 ms
26,668 KB |
testcase_02 | AC | 10 ms
26,792 KB |
testcase_03 | AC | 10 ms
26,796 KB |
testcase_04 | AC | 11 ms
30,756 KB |
testcase_05 | AC | 11 ms
30,912 KB |
testcase_06 | AC | 11 ms
28,876 KB |
testcase_07 | AC | 11 ms
30,780 KB |
testcase_08 | AC | 11 ms
26,792 KB |
testcase_09 | AC | 10 ms
26,792 KB |
testcase_10 | AC | 11 ms
28,748 KB |
testcase_11 | AC | 11 ms
26,664 KB |
testcase_12 | AC | 12 ms
28,744 KB |
testcase_13 | AC | 11 ms
26,796 KB |
testcase_14 | AC | 11 ms
26,796 KB |
testcase_15 | AC | 12 ms
30,888 KB |
testcase_16 | AC | 12 ms
30,904 KB |
testcase_17 | AC | 11 ms
30,888 KB |
testcase_18 | AC | 11 ms
28,880 KB |
testcase_19 | AC | 11 ms
26,792 KB |
testcase_20 | AC | 11 ms
26,920 KB |
testcase_21 | AC | 12 ms
28,872 KB |
testcase_22 | AC | 12 ms
26,796 KB |
testcase_23 | AC | 11 ms
28,872 KB |
testcase_24 | AC | 11 ms
28,748 KB |
testcase_25 | AC | 10 ms
26,796 KB |
testcase_26 | AC | 11 ms
28,748 KB |
testcase_27 | AC | 12 ms
26,792 KB |
testcase_28 | AC | 12 ms
26,792 KB |
testcase_29 | AC | 11 ms
28,876 KB |
testcase_30 | AC | 12 ms
30,880 KB |
testcase_31 | AC | 11 ms
28,752 KB |
testcase_32 | AC | 11 ms
28,880 KB |
testcase_33 | AC | 11 ms
26,796 KB |
testcase_34 | AC | 10 ms
26,660 KB |
testcase_35 | AC | 11 ms
26,792 KB |
testcase_36 | AC | 12 ms
28,748 KB |
testcase_37 | AC | 11 ms
26,792 KB |
testcase_38 | AC | 11 ms
26,796 KB |
testcase_39 | AC | 12 ms
28,748 KB |
testcase_40 | AC | 11 ms
28,876 KB |
testcase_41 | AC | 11 ms
28,740 KB |
コンパイルメッセージ
; compiling file "/home/judge/data/code/Main.lisp" (written 18 SEP 2024 11:24:30 PM): ; file: /home/judge/data/code/Main.lisp ; in: SB-C:DEFTRANSFORM ARRAY-ELEMENT-TYPE ; (SB-C:DEFTRANSFORM ARRAY-ELEMENT-TYPE ; ((ARRAY)) ; (LET ((TYPE (SB-C::LVAR-TYPE ARRAY))) ; (FLET ((ELEMENT-TYPE # ; #)) ; (COND (#) (# #) (# #) (T #))))) ; ; caught STYLE-WARNING: ; Overwriting #<SB-C::TRANSFORM FUNCTION {100033B4E3}> ; in: DEFUN MAIN ; (AREF POLY 1) ; ; note: unable to ; optimize ; due to type uncertainty: ; The first argument is a (SIMPLE-ARRAY * (*)), not a SIMPLE-STRING. ; ; note: unable to ; avoid runtime dispatch on array element type ; because: ; Upgraded element type of array is not known at compile time. ; (POLY-POWER BASE N DIVISOR +MOD+) ; --> BLOCK LABELS RECUR BLOCK COND IF IF OR LET LET POLY-MOD! POLY-MULT BLOCK ; --> LET* LOOP BLOCK LET TAGBODY UNLESS IF ZEROP ; ==> ; 1 ; ; note: unable to ; optimize ; due to type uncertainty: ; The first argument is a (SIMPLE-ARRAY * (*)), not a SIMPLE-STRING. ; ; note: unable to ; avoid runtime dispatch on array element type ; because: ; Upgraded element type of array is not known at compile time. ; ; note: unable to ; open-code FLOAT to RATIONAL comparison ; due to type uncertainty: ; The first argument is a NUMBER, not a SINGLE-FLOAT. ; ; note: unable to ; open-code FLOAT to RATIONAL comparison ; due to type uncertainty: ; The first argument is a NUMBER, not a DOUBLE-FLOAT. ; ; note: unable to ; open-code FLOAT to RATIONAL comparison ; due to type uncertainty: ; The first argument is a NUMBER, not a (COMPLEX SINGLE-FLOAT). ; ; note: unable to ; open-code FLOAT to RATIONAL comparison ; due to type uncertainty: ; The first argument is a NUMBER, not a (COMPLEX DOUBLE-FLOAT). ; ; note: unable to open code because: The operands might not be the same type. ; ; note: unable to ; optimize ; due to type uncertainty: ; The
ソースコード
;; -*- coding: utf-8 -*- (eval-when (:compile-toplevel :load-toplevel :execute) (sb-int:defconstant-eqx OPT #+swank '(optimize (speed 3) (safety 2)) #-swank '(optimize (speed 3) (safety 0) (debug 0)) #'equal) #+swank (ql:quickload '(:cl-debug-print :fiveam) :silent t) #-swank (set-dispatch-macro-character #\# #\> (lambda (s c p) (declare (ignore c p)) (read s nil nil t)))) #+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax) #-swank (disable-debugger) ; for CS Academy ;; BEGIN_INSERTED_CONTENTS ;;; ;;; ARRAY-ELEMENT-TYPE is not constant-folded on SBCL version earlier than ;;; 1.5.0. See ;;; https://github.com/sbcl/sbcl/commit/9f0d12e7ab961828931d01c0b2a76a5885ad35d2 ;;; (eval-when (:compile-toplevel :load-toplevel :execute) (sb-c:deftransform array-element-type ((array)) (let ((type (sb-c::lvar-type array))) (flet ((element-type (type) (and (sb-c::array-type-p type) (sb-int:neq (sb-kernel::array-type-specialized-element-type type) sb-kernel:*wild-type*) (sb-kernel:type-specifier (sb-kernel::array-type-specialized-element-type type))))) (cond ((let ((type (element-type type))) (and type `',type))) ((sb-kernel:union-type-p type) (let (result) (loop for type in (sb-kernel:union-type-types type) for et = (element-type type) unless (and et (if result (equal result et) (setf result et))) do (sb-c::give-up-ir1-transform)) `',result)) ((sb-kernel:intersection-type-p type) (loop for type in (sb-kernel:intersection-type-types type) for et = (element-type type) when et return `',et finally (sb-c::give-up-ir1-transform))) (t (sb-c::give-up-ir1-transform))))))) ;; NOTE: These are poor man's utilities for polynomial arithmetic. NOT ;; sufficiently equipped in all senses. (declaim (inline poly-value)) (defun poly-value (poly x modulus) "Returns the value f(x)." (declare (vector poly)) (let ((x^i 1) (res 0)) (declare (fixnum x^i res)) (dotimes (i (length poly)) (setq res (mod (+ res (* x^i (aref poly i))) modulus)) (setq x^i (mod (* x^i x) modulus))) res)) ;; naive multiplication in O(n^2) (declaim (inline poly-mult)) (defun poly-mult (u v modulus &optional result-vector) "Multiplies u(x) and v(x) over Z/nZ in O(deg(u)deg(v)) time. The result is stored in RESULT-VECTOR if it is given, otherwise a new vector is created." (declare (vector u v) ((or null vector) result-vector) ((integer 1 #.most-positive-fixnum) modulus)) (let* ((deg1 (loop for i from (- (length u) 1) downto 0 while (zerop (aref u i)) finally (return i))) (deg2 (loop for i from (- (length v) 1) downto 0 while (zerop (aref v i)) finally (return i))) (len (max 0 (+ deg1 deg2 1))) (res (or result-vector (make-array len :element-type (array-element-type u))))) (declare ((integer -1 (#.array-total-size-limit)) deg1 deg2 len)) (dotimes (d len res) ;; 0 <= i <= deg1, 0 <= j <= deg2 (loop with coef of-type (integer 0 #.most-positive-fixnum) = 0 for i from (max 0 (- d deg2)) to (min d deg1) for j = (- d i) do (setq coef (mod (+ coef (* (aref u i) (aref v j))) modulus)) finally (setf (aref res d) coef))))) (declaim (ftype (function * (values (mod #.most-positive-fixnum) &optional)) %mod-inverse)) (defun %mod-inverse (a modulus) "Solves ax ≡ 1 mod m. A and M must be coprime." (declare (optimize (speed 3)) (integer a) ((integer 1 #.most-positive-fixnum) modulus)) (labels ((%gcd (a b) (declare (optimize (safety 0)) ((integer 0 #.most-positive-fixnum) a b)) (if (zerop b) (values 1 0) (multiple-value-bind (p q) (floor a b) ; a = pb + q (multiple-value-bind (v u) (%gcd b q) (declare (fixnum u v)) (values u (the fixnum (- v (the fixnum (* p u)))))))))) (mod (%gcd (mod a modulus) modulus) modulus))) ;; naive division in O(n^2) ;; Reference: http://web.cs.iastate.edu/~cs577/handouts/polydivide.pdf (declaim (inline poly-floor!)) (defun poly-floor! (u v modulus &optional quotient) "Returns the quotient q(x) and the remainder r(x) over Z/nZ: u(x) = q(x)v(x) + r(x), deg(r) < deg(v). This function destructively modifies U. The time complexity is O((deg(u)-deg(v))deg(v)). The quotient is stored in QUOTIENT if it is given, otherwise a new vector is created. Note that MODULUS and V[deg(V)] must be coprime." (declare (vector u v) ((integer 1 #.most-positive-fixnum) modulus)) ;; m := deg(u), n := deg(v) (let* ((m (loop for i from (- (length u) 1) downto 0 while (zerop (aref u i)) finally (return i))) (n (loop for i from (- (length v) 1) downto 0 unless (zerop (aref v i)) do (return i) finally (error 'division-by-zero :operation #'poly-floor! :operands (list u v)))) (quot (or quotient (make-array (max 0 (+ 1 (- m n))) :element-type (array-element-type u)))) ;; FIXME: Is it better to signal an error in non-coprime case? (inv (%mod-inverse (aref v n) modulus))) (declare ((integer -1 (#.array-total-size-limit)) m n)) (loop for k from (- m n) downto 0 do (setf (aref quot k) (mod (* (aref u (+ n k)) inv) modulus)) (loop for j from (+ n k -1) downto k do (setf (aref u j) (mod (- (aref u j) (* (aref quot k) (aref v (- j k)))) modulus)))) (loop for i from (- (length u) 1) downto n do (setf (aref u i) 0) finally (return (values quot u))))) ;; naive division in O(n^2) (declaim (inline poly-mod!)) (defun poly-mod! (poly divisor modulus) "Returns the remainder of POLY divided by DIVISOR over Z/nZ. This function destructively modifies POLY." (declare (vector poly divisor) ((integer 1 #.most-positive-fixnum) modulus)) (let* ((m (loop for i from (- (length poly) 1) downto 0 while (zerop (aref poly i)) finally (return i))) (n (loop for i from (- (length divisor) 1) downto 0 unless (zerop (aref divisor i)) do (return i) finally (error 'division-by-zero :operation #'poly-mod! :operands (list poly divisor)))) (inv (%mod-inverse (aref divisor n) modulus))) (declare ((integer -1 (#.array-total-size-limit)) m n)) (loop for pivot-deg from m downto n for factor of-type (integer 0 #.most-positive-fixnum) = (mod (* (aref poly pivot-deg) inv) modulus) do (loop for delta from 0 to n do (setf (aref poly (- pivot-deg delta)) (mod (- (aref poly (- pivot-deg delta)) (* factor (aref divisor (- n delta)))) modulus)))) poly)) (declaim (inline poly-power)) (defun poly-power (poly exponent divisor modulus) "Returns POLY to the power of EXPONENT modulo DIVISOR over Z/nZ." (declare (vector poly divisor) ((integer 0 #.most-positive-fixnum) exponent) ((integer 1 #.most-positive-fixnum) modulus)) (labels ((recur (power) (declare ((integer 0 #.most-positive-fixnum) power)) (cond ((zerop power) (make-array 1 :element-type (array-element-type poly) :initial-element 1)) ((oddp power) (poly-mod! (poly-mult poly (recur (- power 1)) modulus) divisor modulus)) ((let ((res (recur (floor power 2)))) (poly-mod! (poly-mult res res modulus) divisor modulus)))))) (recur exponent))) (defmacro dbg (&rest forms) #+swank (if (= (length forms) 1) `(format *error-output* "~A => ~A~%" ',(car forms) ,(car forms)) `(format *error-output* "~A => ~A~%" ',forms `(,,@forms))) #-swank (declare (ignore forms))) (defmacro define-int-types (&rest bits) `(progn ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "UINT~A" b)) () '(unsigned-byte ,b))) bits) ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "INT~A" b)) () '(signed-byte ,b))) bits))) (define-int-types 2 4 7 8 15 16 31 32 62 63 64) (declaim (inline println)) (defun println (obj &optional (stream *standard-output*)) (let ((*read-default-float-format* 'double-float)) (prog1 (princ obj stream) (terpri stream)))) (defconstant +mod+ 1000000007) ;;; ;;; Body ;;; (defun main () (declare #.OPT) (let* ((a (read)) (b (read)) (n (read)) (divisor (coerce (list (- +mod+ b) (- +mod+ a) 1 0 0 0) '(simple-array uint32 (*)))) (base (make-array 6 :element-type 'uint32 :initial-contents '(0 1 0 0 0 0))) (poly (poly-power base n divisor +mod+))) (declare (uint32 a b) ((simple-array uint32 (*)) divisor base)) (println (aref poly 1)))) #-swank (main)