注意:この記事は未完成です。こちらの記事を参考にお願いします
wakabame.hatenablog.com
の素数 で割った余りを求める方法について解説します. は" 個の異なるものから 個を選ぶときの組み合わせの数"を表しており, 階乗記号 を用いて,
と表されます. 階乗の大きさは指数関数的に増大していくので, 分母と分子は非常に大きな数になりえます. 素数 で割った余りさえわかればよいことを用いて, どうにか計算量を減らしていきましょう.
続きを読む注意:この記事は未完成です。こちらの記事を参考にお願いします
wakabame.hatenablog.com
の素数 で割った余りを求める方法について解説します. は" 個の異なるものから 個を選ぶときの組み合わせの数"を表しており, 階乗記号 を用いて,
と表されます. 階乗の大きさは指数関数的に増大していくので, 分母と分子は非常に大きな数になりえます. 素数 で割った余りさえわかればよいことを用いて, どうにか計算量を減らしていきましょう.
続きを読む整数 と整数 に対して, を整数 で割った余りを出力します. 安直に を 回乗じてからで割れば良いのではないかと考えたくなりますが, この方法には2つの欠点があります.
この2点を解消する方法について解説します.
続きを読むワーシャル=フロイド法を用いた問題演習として, AtCoder Beginner Contest 074 の D 問題の解説をしてみます.
問題はこちら
abc074.contest.atcoder.jp
これは制限時間内に解けませんでした.
今回は有向グラフの情報が与えられたとき, 全ての始点から全ての終点までの最短距離をワーシャル=フロイド(Warshall–Floyd)法と呼ばれるアルゴリズムで求めていきます. 有向グラフの最短距離を求めるアルゴリズムのうち, ベルマン=フォード法は以前紹介しました:
wakabame.hatenablog.com
今回紹介するワーシャル=フロイド法では, 頂点の集合を としたとき, 任意の頂点 に対してその間の最短距離を一挙に計算してしまいます. その代わり, 計算量は とやや大量になってしまいます.
有向グラフ(directed graph)とは, 頂点(vertex)と辺(edge)からなり, 辺は の形式を持ち, 頂点 から頂点 へはコスト で移動できることを表しています. 辺に対して逆向きの進路があるとは限らず, あったとしても同じコストとは限りません.
今回はグラフの情報と始点が与えられたとき, 各頂点への最短距離をベルマン=フォード法と呼ばれるアルゴリズムで求めていきます.
また, 有向グラフ上の2点間の最短距離を求めるアルゴリズムにはダイクストラ(Dijkstra)法と呼ばれるものもありますが, ベルマン=フォード法の強みは辺の重みは負でもよいことが挙げられます.
一方, 負の重みを持つ辺があるときに考えなくてはならないのは負閉路の検出です. 閉路を一周するごとに距離をマイナスにすることができるものが存在する場合, その閉路を何度も通ることで最短距離をいくらでも縮めることができてしまい, 最短経路が定まりません. ですので負閉路が存在(かつ始点から到達)する場合には最短距離の代わりに警告を返します.
木構造の距離を求める問題演習として, AtCoder Beginner Contest 070 の D 問題の解説をしてみます.
問題はこちら
abc070.contest.atcoder.jp