結果

問題 No.660 家を通り過ぎないランダムウォーク問題
ユーザー Common LispCommon Lisp
提出日時 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

ソースコード

diff #
プレゼンテーションモードにする

(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)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0