dkh.functional
-
Declaration
struct memoCont(alias pred);メモ化ライブラリ
Discussion
std.functional.memoizeとは違い, 引数が連続している必要がある. ハッシュテーブルではなく配列で値を保存するため高速である.
Examples
import dkh.numeric.primitive; import dkh.modint; alias Mint = ModInt!(10^^9+7); struct A { static auto fact = factTable!Mint(100); static auto iFac = invFactTable!Mint(100); static Mint C1(int n, int k) { return fact[n] * iFac[k] * iFac[n-k]; } // メモ化再帰でnCkの計算をする static memoCont!C2base C2; static Mint C2base(int n, int k) { if (k == 0) return Mint(1); if (n == 0) return Mint(0); return C2(n-1, k-1) + C2(n-1, k); } } // 0 <= n <= 99, 0 <= k <= 99, 閉区間 A.C2.init([[0, 99], [0, 99]]); foreach (i; 0..100) { foreach (j; 0..i+1) { assert(A.C1(i, j) == A.C2(i, j)); } }