「写像12相」で典型的な数え上げ問題のパターン総整理
条件を満たすものが何通りあるか数える問題、すなわち数え上げ問題には様々なものがありますが、「\(n\) 個の玉を \(x\) 個の箱に分ける方法は何通りか」などといった、典型的なものはある程度パターン化して解くことができます。 ...
自然数nをk個の0以上の整数に分割する方法の総数を求めるアルゴリズム
以下の2つを混同しそうですが、ここでは \(p_{\leq k}(n)\) を求めることを考えます。
\(p_k(n)\) : 自然数 \(n\) を \(k\) 個の 1 以上の整数に分割する方法の数。言い換えると、区別できな ...自然数nをk個の1以上の整数に分割する方法の総数を求めるアルゴリズム
以下の2つを混同しそうですが、ここでは \(p_k(n)\) を求めることを考えます。
\(p_k(n)\) : 自然数 \(n\) を \(k\) 個の 1 以上の整数に分割する方法の数。言い換えると、区別できない \(n\) ...木DPと全方位木DPを基礎から抽象化まで解説【競技プログラミング】
競技プログラミングでよく出題される木DPについての説明と、木DPで解ける一部の問題を同じ計算量で全頂点について求められるように応用した全方位木DPについて解説します。
木DP基本的な考え方とイメージ木DP とは、根を一つ固 ...
N – 木 解説（AtCoder Typical DP Contest）
問題へのリンク
問題概要木が与えられる。辺が常に連結になるように木を描く。何通りの描き方があるか、mod 1,000,000,007 で求めよ。
制約\(2 \leq N \leq 1000 \)考え方前提： ...
パスカルの三角形による二項係数(nCk)の計算
以下のような「上の2つを足して下の数字をつくる三角形」をパスカルの三角形といい、上から \(n\) 行目・左から \(k\) 個目の数は、\(_{n}\mathrm{C}_{k}\) に対応しています。(0-indexed)
二項係数(nCk)を素数(p)で割った余りの計算（Lucas の定理）
Lucas の定理を利用すると、\(_{n}\mathrm{C}_{k}\)% \(p\) が \(O( p^2 \log_p n)\) で計算できます。素数 \(p\) が小さい場合は十分高速です。
Lucas の定理任 ...
ビットDP(bit DP)の考え方 ~集合に対する動的計画法~
競技プログラミングで良く使われる動的計画法の1種、「ビットDP」と呼ばれるものについてまとめました。
ビットDPとはビットDP(bit DP) とは、ビットで表現した集合を添え字に持つ動的計画法(DP)のことです。 ...
[AtCoder] ABC154 E – Almost Everywhere Zero (500点)
問題へのリンク
問題概要1 以上 N 以下の整数で、0 でない数字がちょうど K 個あるものの個数を求めよ。
制約\begin{align}
&1 \leq N \leq 10^{100} \\ ...
動的計画法（Dynamic Programming）入門
動的計画法（Dynamic Programming）とは、小さい部分問題を計算して記録しておき、より大きい問題を計算する際に利用する手法のことです。
以下のような特徴がありますが、抽象的なのでここではざっと眺 ...