結果

問題 No.660 家を通り過ぎないランダムウォーク問題
コンテスト
ユーザー keiden
提出日時 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))))))
0