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

問題へのリンク

問題概要

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

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

数学二項係数, 動的計画法, パスカルの三角形

以下のような「上の2つを足して下の数字をつくる三角形」をパスカルの三角形といい、上から \(n\) 行目・左から \(k\) 個目の数は、\(_{n}\mathrm{C}_{k}\) に対応しています。(0-indexed)

数学剰余, 二項係数, Lucasの定理, 素数の剰余, 偶奇性

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

アルゴリズム

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

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

数学剰余, 二項係数, 動的計画法, Lucasの定理, 素数の剰余

Lucas の定理を利用すると、\(_{n}\mathrm{C}_{k}\)% \(p\) が \(O( p^2 \log_p n)\) で計算できます。素数 \(p\) が小さい場合は十分高速です。

Lucas の定理

任 ...

2020年2月24日AtCoder剰余, 二項係数, 操作, 数え上げ, 500点, 重複組合せ

問題概要

n 個の部屋に 1 ずつ人がいる。以下を k 回行ったとき、考えられる状態は何通りあるか \(10^9+7\) で割った余りで答えよ。

ある部屋 \(i\) にいた人が、\(i \neq j\) を満たす任意の部屋 \( ...

2020年2月10日AtCoder二項係数, 600点, 二次元, 区間和

問題へのリンク

問題概要

2次元の平面上で、以下のように関数 f(r,c) を定義する。

f(r,c) := (0,0)から(r,c)までの経路の個数

この時、以下を計算せよ。ただし、\(10^9+7 ...

2019年12月4日数学剰余, 二項係数, テーマ記事, 競プロ, 素数, 逆元

競技プログラミングの問題などでは、二項係数を非常に大きい素数 P で割った余りを出力させる問題が出題されることがあります。 \(P = 1000000007 = 10^9 + 7\) の素数を使用することなどが多いです。

...