剰余

問題へのリンク

問題概要

町が \(N\) 個ある。町 \(i\) から町 \(A_i\) に移動することを K 回繰り返す。
町 1 から始めた時、最終的にどの町にたどり着くか？

制約\(2 \leq N \ ...

問題へのリンク

問題概要

\(N\) が \(K\) 未満になるまで以下の操作を繰り返す時、最終的に 1 になるような \(K\) が何通り存在するか答えよ。

\(N\) が \(K\) で割り切れる：\(N\) を ...

問題へのリンク

問題概要

木が与えられる。辺が常に連結になるように木を描く。何通りの描き方があるか、mod 1,000,000,007 で求めよ。

制約\(2 \leq N \leq 1000 \)
考え方前提： ...

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

アルゴリズム

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

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

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

Lucas の定理

任 ...

問題概要

長さ N の数 S が与えられる。
素数 P で割り切れるような区間の選び方は何通りあるか？

制約\(1 \leq N \leq 2 \times 10^5\)
\(2 \leq P \leq 10000\ ...

問題概要

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

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

多くのプログラミング言語でサポートされてる \(x^n\) を計算する関数のアルゴリズムです。

Input : pow(2,4) (x=2, n=4)
Output : 16

べき乗は非常に大きな数値に ...

問題へのリンク

問題

一部が ? で与えられる数字の文字列 S について、13で割って5余る数で考えられる物は何通りあるか。
答えを 1e9+7 で割った余りで答えよ。

制約\(1 \leq |S| \leq ...

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

...