結果
問題 | No.660 家を通り過ぎないランダムウォーク問題 |
ユーザー |
![]() |
提出日時 | 2024-11-15 15:50:15 |
言語 | Common Lisp (sbcl 2.5.0) |
結果 |
AC
|
実行時間 | 91 ms / 2,000 ms |
コード長 | 1,853 bytes |
コンパイル時間 | 390 ms |
コンパイル使用メモリ | 37,520 KB |
実行使用メモリ | 46,208 KB |
最終ジャッジ日時 | 2024-11-15 15:50:20 |
合計ジャッジ時間 | 4,614 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 45 |
コンパイルメッセージ
; compiling file "/home/judge/data/code/Main.lisp" (written 15 NOV 2024 03:50:15 PM): ; wrote /home/judge/data/code/Main.fasl ; compilation finished in 0:00:00.089
ソースコード
(defconstant +mod+ 1000000007)(defun %mod-inverse (a_ m_)(let ((a a_)(m m_)(b m_)(u 1)(v 0))(loop while (plusp b) do(let ((s (floor a b)))(decf a (* s b))(rotatef a b)(decf u (* s v))(rotatef u v)))(mod u m)))(defvar *mod-fact* (make-array 1000001 :element-type 'integer))(defvar *mod-fact-inv* (make-array 1000001 :element-type 'integer))(defvar *mod-inv* (make-array 1000001 :element-type 'integer))(defun %init-mod-combination (n m)(setf (aref *mod-fact* 0) 1(aref *mod-fact-inv* n) 1(aref *mod-inv* 0) 1)(loop for i from 1 to n do(setf (aref *mod-fact* i) (mod (* i (aref *mod-fact* (1- i))) m)))(setf (aref *mod-fact-inv* n) (%mod-inverse (aref *mod-fact* n) m))(loop for i from (1- n) downto 0 do(setf (aref *mod-fact-inv* i) (mod (* (aref *mod-fact-inv* (1+ i)) (1+ i)) m)))(loop for i from 1 to n do(setf (aref *mod-inv* i) (mod (* (aref *mod-fact* (1- i)) (aref *mod-fact-inv* i)) m))))(defun %mod-nCk (n k m)(if (or (minusp k) (< n k))0(mod (* (aref *mod-fact* n) (aref *mod-fact-inv* k) (aref *mod-fact-inv* (- n k))) m)))(defun %mod-nPk (n k m)(if (or (minusp k) (< n k))0(mod (* (aref *mod-fact* n) (aref *mod-fact-inv* (- n k))) m)))(defun %mod-nHk (n k m)(if (= n k 0)1(%mod-nCk (+ n k -1) k m)))(defun main (&rest argv)(declare (ignorable argv))(%init-mod-combination 500001 +mod+)(let* ((n (read))(res 0)(k 0))(loop for i from (1- n) below (* 2 n) by 2 do(let ((x (%mod-nCk i (+ n k -1) +mod+))(y (%mod-nCk i (+ n k) +mod+)))(incf k)(setq res (mod (+ res x (- y)) +mod+))))(format t "~d~%" res)))(main)