結果

問題 No.129 お年玉(2)
ユーザー jj
提出日時 2016-10-10 18:14:21
言語 Fortran
(gFortran 14.2.0)
結果
AC  
実行時間 721 ms / 5,000 ms
コード長 867 bytes
コンパイル時間 216 ms
コンパイル使用メモリ 31,488 KB
実行使用メモリ 393,856 KB
最終ジャッジ日時 2024-11-28 00:36:45
合計ジャッジ時間 24,884 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff # 

program main
  implicit none
  integer*8::N,M,amari
  integer*4,parameter::sen=1000
  integer*4::memo(10**4,0:10**4)
  data memo/100010000*0/

  read *,N,M
  N = N/sen
  amari = MOD(N, M)
  memo = 0
  print '(i0)', get_combination(M, MIN(amari, M-amari), memo)
contains
  recursive function get_combination(N,R, memo) result(NCR)
    integer*8::N,R,NCR
    integer*4,parameter::modular=10**9
    integer*4::memo(10**4,0:10**4)
    if(memo(N,R).ne.0) then
       NCR = memo(N,R)
    else
       if(R.eq.0) then
          NCR = 1
       else if(R.eq.1) then
          NCR = N
       else if(N-R.lt.R) then
          NCR = get_combination(N, N-R, memo)
       else
          NCR = get_combination(N-1,R,memo) + get_combination(N-1,R-1,memo)
       end if
       NCR = MOD(NCR, modular)
       memo(N,R) = NCR
    end if
   end function get_combination
 end program main
0