コンテストページ
http://abc021.contest.atcoder.jp

解説スライド

AtCoder Beginner Contest 021 解説 from chokudai

結果

oo--

A 足し算

省略

B 嘘つきの高橋くん

省略

C 正直者の高橋くん

単一始点最短路問題

辺に重みがない（＝重みがすべて1）の場合

幅優先探索 $\mathcal{O}(E)$

重みが負の辺がある場合

ベルマンフォード法 $\mathcal{O}(VE)$

重みが負の辺がない場合

ダイクストラ法 $\mathcal{O}(Elog(V))$

解法

最短距離とその点までの最短経路が何通りあるかを各点ごとに持ちながら幅優先探索する

ソースコード

D 多重ループ

重複組合せ

$n$種のものから重複を許し$k$個を選ぶ選び方 … ${}_nH_k$

$k$個を$n$種に分ける分け方と同じ。
$n-1$個の仕切りがあれば$n$種に振り分けられる。

$$ {}_nH_k = \frac{(n-1+k)!}{(n-1)!k!} = {}_{n+k - 1} C_k $$

$k$個があって隙間$k + 1$個に$n-1$本の仕切りを入れることでn種に分けると考えることもできるので

$$ {}_n H_k = {}_{k + 1}H_{n-1} $$

ある1種に着目して、その1種が1つも含まれない場合と、少なく1つ含まれる場合が考えられるので

$$ {}_n H_k = {}_{n - 1}H_k + {}_{n}H_{k - 1} $$

n種目を0~k個使い残りをn-1種から選ぶ場合の数の和がn種からk個選ぶ場合の数なので

$$ {}_nH_k = \sum_{i=0}^k {}_nH_{k-i} = \sum_{i=0}^k {}_nH_i $$

これを繰り返し用いれば、${}_1H_k = 1$なので

$$ {}_nH_k = \sum_{i_{n-1}=0}^k \sum_{i_{n-2}=0}^{i_{n-1}} \dots \sum_{i_1=0}^{i_2} $$

フェルマーの小定理

$p$が素数、$a$が任意の自然数のとき

$$
a^p \equiv a \pmod{m}
$$

特に$a$と$p$が互いに素な自然数の時

$$
a^{p-1} \equiv 1 \pmod{m}
$$

解法

解説スライドの通りなので省略