組合せ

 1type combination struct {
 2	fact, ifact, inv []int
 3	m              int
 4}
 5
 6func newCombination(n, M int) *combination {
 7	fact := make([]int, n+1)
 8	ifact := make([]int, n+1)
 9	inv := make([]int, n+1)
10
11	fact[0], fact[1] = 1, 1
12	ifact[0], ifact[1] = 1, 1
13	inv[1] = 1
14
15	for i := 1; i < n; i++ {
16		fact[i+1] = fact[i] * (i + 1) % M
17		inv[i+1] = M - inv[M%(i+1)]*(M/(i+1))%M
18		ifact[i+1] = ifact[i] * inv[i+1] % M
19	}
20
21	return &combination{fact, ifact, inv, M}
22}
23
24func (c *combination) P(m, n int) int {
25	return c.fact[m] * c.ifact[m-n] % c.m
26}
27func (c *combination) C(m, n int) int {
28	return c.fact[m] * c.ifact[n] % c.m * c.ifact[m-n] % c.m
29}
30func (c *combination) H(n, r int) int {
31	return c.C(n+r-1, r)
32}
33