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