memoCont

1 import dkh.numeric.primitive;
2 import dkh.modint;
3 alias Mint = ModInt!(10^^9+7);
4 
5 struct A {
6     static auto fact = factTable!Mint(100);
7     static auto iFac = invFactTable!Mint(100);
8     static Mint C1(int n, int k) {
9         return fact[n] * iFac[k] * iFac[n-k];
10     }
11 
12     // メモ化再帰でnCkの計算をする
13     static memoCont!C2base C2;
14     static Mint C2base(int n, int k) {
15         if (k == 0) return Mint(1);
16         if (n == 0) return Mint(0);
17         return C2(n-1, k-1) + C2(n-1, k);
18     }
19 }
20 
21 // 0 <= n <= 99, 0 <= k <= 99, 閉区間
22 A.C2.init([[0, 99], [0, 99]]);
23 foreach (i; 0..100) {
24     foreach (j; 0..i+1) {
25         assert(A.C1(i, j) == A.C2(i, j));
26     }
27 }