Combination Table

combination_table is a small helper module that lazily builds tables for binomial coefficients and factorials.

It can be called in a method-like style, such as int.C(n, r).

Import

import atcoder/extra/math/combination_table

Example

import atcoder/extra/math/combination_tabledoAssert int.C(5, 2) == 10doAssert int.H(3, 2) == 6doAssert int.P(5, 2) == 20doAssert int.fact(5) == 120

API

C

T.C(n, r)

Returns the binomial coefficient n choose r. Out-of-range values return 0.

H

T.H(n, r)

Returns the number of combinations with repetition.

P

T.P(n, r)

Returns the number of permutations.

fact

T.fact(k)

Returns k!.

resetCombination

T.resetCombination()

Clears the internal tables.

Complexity

Tables are extended lazily.

• first construction up to a new n: O(n^2)
• query within the already built range: O(1)