@numba.njit def makeCombibationTableJointedNoReshapeNumba(N): """ make table of C(n, i) for i in [0, N) Jointed version of makeFactorialTableMaspy, makeInvFactoTableMaspyOriginal, and makeCombibationTableMaspy. >>> list(makeCombibationTableJointedNumba(10000)[:5]) [1, 10000, 49995000, 616668838, 709582588] %timeit makeCombibationTableJointedNoReshapeNumba(K) 33 ms ± 809 µs per loop (mean ± std. dev. of 7 runs, 10 loops each) """ K = math.ceil(math.sqrt(N + 1)) ** 2 rootK = math.ceil(math.sqrt(K)) facto = np.arange(K, dtype=np.int64) facto[0] = 1 for i in range(1, rootK): facto[i::rootK] *= facto[i-1::rootK] facto[i::rootK] %= MOD for start in range(rootK, K, rootK): end = start + rootK facto[start:end] *= facto[start - 1] facto[start:end] %= MOD invf = np.arange(1, K + 1, dtype=np.int64) invf[-1] = getSingleInverseNumba(facto[K - 1]) # inverse of (k-1)! for pos in range(rootK - 2, -1, -1): invf[pos::rootK] *= invf[pos + 1::rootK] invf[pos::rootK] %= MOD for end in range(-rootK, -K, -rootK): start = end - rootK invf[start:end] *= invf[end] invf[start:end] %= MOD return facto[N] * invf[:N + 1] % MOD * invf[N::-1] % MOD