AtCoder Beginner Contest 034 A, B, C

abc034.contest.atcoder.jp

B

偶数の人は一つ手前の人と、奇数の人は一つ後の人とペアになる。

Submission #935372 - AtCoder Beginner Contest 034 | AtCoder

C

整数論を用いる。前に使ったことがあるので、それを思い出しながら

1,000,000,007が素数なので、フェルマーの小定理より、

a^p \equiv a (mod p)

a^{p-1} \equiv 1 (mod p)

a^{p-2} \equiv a^{-1} (mod p)

これで、


\begin{eqnarray}
  {}_n C_{k} &=& \frac{n!}{(n-k)!k!} \\
&=& n! \cdot (r!)^{-1} \cdot {(n-r)!}^{-1} \\
&=& n! \cdot (r!)^{p-2} \cdot \{(n-r)!\}^{p-2} \pmod{p}
\end{eqnarray}

応用問題:D: いろはちゃんとマス目 / Iroha and a Grid - AtCoder Beginner Contest 042 | AtCoder

Submission #935391 - AtCoder Beginner Contest 034 | AtCoder