2026.09.04

記事内に商品プロモーションを含む場合があります

【Go言語】mod付きの組み合わせ（nCk）を高速に計算する

Aru

競技プログラミング（AtCoder）では、大きな数を取り扱う場合に「1000000007で割った余りを求めよ」というように剰余（mod）で答える問題が登場します。組み合わせ数（combination, choose）を答える問題では、剰余で答えることが多いです。

この記事では、組み合わせ数 ${}_nC_k$ を剰余付きで求める方法と、何度も組み合わせ数を答える場合に高速に求める方法を、Go言語で解説します。

同じ内容を Python で以前にまとめたことがあるので、今回はその Go 版になります。

剰余演算（MOD演算）

剰余演算とは

剰余演算（modulo演算）は、ある数を別の数で割った際の余りを計算する演算です。プログラミングでは a % b で表します。

r := 10 % 3 // r = 1

AtCoder では、結果が int64（64bit整数）を超える場合に剰余演算が使われます。

組み合わせ計算ではあっという間に桁が爆発するので、AtCoder では「剰余で答えよ」という指定がとても多いです

組み合わせの公式

「n個の中からk個を取り出す組み合わせの場合の数」は ${}_nC_k$ と表記します（C は Combination（組合せ）の頭文字です）。

${}_nC_k$ は以下の公式で求めることができます。

$$
{}_nC_k = \frac{n!}{k! (n-k)!}
$$

この式を見ればわかるように、$n!$, $k!$, $(n-k)!$ という階乗がそれぞれ計算できれば組み合わせは計算が可能です。

ただし、$k!$ や $(n-k)!$ については $\frac{1}{k!}$, $\frac{1}{(n-k)!}$ を求める必要があります。この「割り算」をうまく扱うために逆元の計算が必要となります。

結局、$x!$と$1/x!$が計算できれば、組み合わせ計算ができることになります。

逆元について

なぜ逆元が必要か

合同式（mod）の場合、割り算はそのまま計算できません。足し算・引き算・掛け算は、そのまま演算して余りを取れば良いのですが、割り算だけは工夫が必要です。

割り算を行うには、フェルマーの小定理を利用します。

フェルマーの小定理

$p$ を素数とし、$a$ を $p$ の倍数でない正数とすると、以下が成立します。

$$
a^{p-1} \equiv 1 \pmod p
$$

これを変形すると、以下の式が導き出せます。

$$
a^{p-2}\cdot a \equiv 1 \pmod p
$$

$a$ に $a^{p-2}$ を掛け合わせると 1 になるということは、$a^{p-2} = \frac{1}{a}$ ということです。つまり $a^{p-2}$ は $a$ の逆元です。

これにより、mod $p$ での $\frac{1}{k!}$, $\frac{1}{(n-k)!}$ が計算できます。

ポイント

mod が素数のとき、$a$ の逆元は $a^{p-2}$ を mod で計算すれば求まる

組み合わせの計算

愚直解の問題点

毎回階乗を計算して組み合わせを求める愚直な方法の場合、1回の ${}_nC_k$ に対して $n-k$ や $k$ の分だけ掛け算と割り算が必要になり、1回あたり O(N)〜O(N log mod)程度かかります。

一度なら問題ないですが、多くの場合nCkの計算を何度も行う必要がある問題が出題されます。なので、毎回階乗を計算していると、クエリの数だけ時間がかかり、実行時間制限に間に合わなくなります（TLE）。

そこで、必要な範囲をあらかじめ計算してテーブル（配列）に保存する必要があるわけです。

階乗（n!）の前計算

fact[i] に $i!$ の結果の事前計算は簡単です。

階乗は以下のコードで $0!$ から $n!$ まで計算できます。

fact := make([]int64, n+1)
fact[0] = 1
for i := 1; i <= n; i++ {
	fact[i] = fact[i-1] * int64(i) % mod
}

これで fact[0]からfact[n] までが、O(N) で計算できました。

逆元（1/n!）の前計算

組み合わせの計算では $\frac{1}{k!}$ などが必要になりますが、すべての fact[k] に対して pow(k, mod-2, mod) を計算すると、pow の計算に時間がかかります。

そこで少し工夫します。具体的には以下のアイデアになります。

$$
\frac{1}{(n-1)!} = \frac{1}{1\times 2 \times \cdots \times (n-2) \times (n-1)}
$$

から、以下の関係が得られます。

$$
\frac{1}{(n-2)!} = \frac{1}{1\times 2 \times \cdots \times (n-2) \times (n-1)} \times (n-1) = \frac{1}{(n-1)!} \times (n-1)
$$

つまり、$\frac{1}{(n-1)!}$ だけフェルマーの小定理で計算し、あとは n から順に掛け算でたどるだけで、すべての逆元を O(N) で求めることができるわけです。

逆元を ifact[i] とすると、以下のコードで前計算できます。このプログラムでは、Powを使った逆元の計算は一回だけです。

// fact[n] の逆元をフェルマーの小定理で計算
ifact[n] = modPow(fact[n], mod-2, mod)

// 逆元を後ろから累積計算
for i := n; i >= 1; i-- {
	ifact[i-1] = ifact[i] * int64(i) % mod
}

コード全体（Comb）

前計算ができれば、あとは組み合わせの数を計算するだけです。Goではクラスがないので構造体にまとめました。

以下は、コピペでそのまま動くコードです。

package main

import "fmt"

type Comb struct {
	n     int
	mod   int64
	fact  []int64
	ifact []int64
}

// 繰り返し二乗法による (base^exp) % mod の計算
func modPow(base, exp, mod int64) int64 {
	res := int64(1)
	base %= mod
	for exp > 0 {
		if exp&1 == 1 {
			res = (res * base) % mod
		}
		base = (base * base) % mod
		exp >>= 1
	}
	return res
}

func NewComb(n int, mod int64) *Comb {
	fact := make([]int64, n+1)
	ifact := make([]int64, n+1)

	fact[0] = 1
	for i := 1; i <= n; i++ {
		fact[i] = (fact[i-1] * int64(i)) % mod
	}

	// n! の逆元をフェルマーの小定理で計算
	ifact[n] = modPow(fact[n], mod-2, mod)

	// 逆元を後ろから O(N) で累積計算
	for i := n; i >= 1; i-- {
		ifact[i-1] = (ifact[i] * int64(i)) % mod
	}

	return &Comb{
		n:     n,
		mod:   mod,
		fact:  fact,
		ifact: ifact,
	}
}

func (c *Comb) nCr(n, r int) int64 {
	if r < 0 || r > n || n > c.n {
		return 0
	}
	return (c.fact[n] * c.ifact[r] % c.mod) * c.ifact[n-r] % c.mod
}

func (c *Comb) nPr(n, k int) int64 {
	if k < 0 || k > n || n > c.n {
		return 0
	}
	return c.fact[n] * c.ifact[n-k] % c.mod
}

func (c *Comb) nHr(n, k int) int64 {
	if n < 0 || k < 0 {
		return 0
	}
	if n == 0 && k == 0 {
		return 1
	}
	return c.nCr(n+k-1, k)
}

func main() {
	comb := NewComb(200100, 998244353)

	fmt.Println(comb.nCr(10, 3))  // 120
	fmt.Println(comb.nCr(10, 11)) // 0
}

計算量

前計算とクエリ計算の計算量を表にまとめます。

手法	前計算	1回のクエリ
毎回階乗を計算（愚直解）	なし	O(N)〜O(N log mod)
階乗＋逆元を前計算（本記事）	O(N)	O(1)

前計算にかかる O(N) は一度だけなので、クエリ数が多いほど高速化の効果が大きくなります。例えば N=200000 程度でも、前計算は余裕で実行時間制限に収まります。

注意点

mod は素数である必要がある
逆元をフェルマーの小定理（$a^{p-2}$）で求めているためです。もし素数でない mod が指定された場合は、別の方法（拡張ユークリッドの互除法）が必要になります
int64 の範囲に注意
$n+k-1$ の計算では、$n$ と $k$ が大きいと int64 の範囲を超える場合があります
前計算サイズ
NewComb(n, mod) の n は、実際に使う最大の $n$ 以上にしておきます。上限がわかっている場合は少し多めに取るとよいです