結果

問題 No.660 家を通り過ぎないランダムウォーク問題
ユーザー keidenkeiden
提出日時 2024-09-23 12:03:43
言語 Scheme
(Gauche-0.9.15)
結果
AC  
実行時間 184 ms / 2,000 ms
コード長 1,463 bytes
コンパイル時間 389 ms
コンパイル使用メモリ 7,072 KB
実行使用メモリ 26,772 KB
最終ジャッジ日時 2024-09-23 12:10:39
合計ジャッジ時間 19,858 ms
ジャッジサーバーID
(参考情報)
judge1 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

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

(define (make-fact-table n mo)
(let*
((ftable (make-vector n 0)))
(vector-set! ftable 0 1)
(do
((i 1 (+ i 1)))
((= i n) ftable)
(vector-set! ftable i (modulo (* (vector-ref ftable (- i 1)) i) mo)))))
(define (make-invfact-table n mo ftable)
(let*
((iftable (make-vector n 0)))
(vector-set! iftable (- n 1) (expt-mod (vector-ref ftable (- n 1)) (- mo 2) mo))
(do
((i (- n 2) (- i 1)))
((< i 0) iftable)
(vector-set! iftable i (modulo (* (vector-ref iftable (+ i 1)) (+ i 1)) mo)))))
(define (nCr n r mo ftable iftable)
(if (or (< r 0) (< n r)) 0 (modulo (* (modulo (* (vector-ref ftable n) (vector-ref iftable r)) mo) (vector-ref iftable (- n r))) mo)))
(define (nPr n r mo ftable iftable)
(if (or (< r 0) (< n r)) 0 (modulo (* (vector-ref ftable n) (vector-ref iftable (- n r))) mo)))
(define (nHr n r mo ftable iftable)
(if (= n r 0) 1 (nCr (- (+ n r) 1) r mo ftable iftable)))
(define yuki660
(let*
(
(max-n 500000)
(mod-1e9p7 1000000007)
(ft (make-fact-table max-n mod-1e9p7))
(ift (make-invfact-table max-n mod-1e9p7 ft))
(n (read))
(r 0)
(ret 0)
)
(do
((i (- n 1) (+ i 2)))
((>= i (* 2 n)) (print ret))
(let*
(
(x (nCr i (- (+ n r) 1) mod-1e9p7 ft ift))
(y (nCr i (+ n r) mod-1e9p7 ft ift))
)
(set! r (+ r 1))
(set! ret (modulo (+ ret (- x y)) mod-1e9p7))))))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0