2020年3月23日AtCoder二項係数,Lucasの定理,偶奇性,パスカルの三角形,差の絶対値

問題へのリンク

問題概要

1,2,3 で構成された整数列 \(a_1 a_2 a_3 \cdots a_N\) が与えられ、\(x_{i,j}\) を以下のように再帰的に定義する。

\(x_{1,j} := a_j\) ...

2020年3月22日数学剰余,二項係数,Lucasの定理,素数の剰余,偶奇性

Lucasの定理を利用することで、二項係数(nCk) が偶数なのか奇数なのかを効率よく判定することができます。

アルゴリズム

Lucasの定理をそのまま利用したアルゴリズム:

\({}_{n_i}\mathrm ...