mayoko’s diary

プロコンとかいろいろ。

2016-08-30から1日間の記事一覧

AOJ 2397 Three-way Branch

AOJ

問題 Three-way Branch | Aizu Online JudgeW*H のグリッドが与えられる。これらのうち, N 個のセルは通れなくなっている。あるセル(x, y) からは (x-1, y+1) or (x, y+1) or (x+1, y+1) にのみ行ける場合, (0, 0) から (W-1, H-1) までの経路は何通りあるか…

Educational Codeforces Round 16 D. Two Arithmetic Progressions

問題 codeforces.comx = a1 * k + b1 = a2 * l + b2, L 解法 k, l の組を一つ求められれば, 後は x が lcm(a1, a2) の周期で解になるので簡単です(実装が楽とは言っていない)。a1 * k + b1 = a2 * l + b2 を変形すると a1 * k - a2 * l = b2 - b1 となります…

Codeforces Round #369 (Div. 2) E. ZS and The Birthday Paradox

問題 codeforces.com整数 n, k が与えられる。p = 2^n として, 1 - (p! / p^k * (p-k)!) の分母と分子を求めよ。ただし分母と分子は非常に大きな値になることがあるので, 10^6+3 で割ったあまりを求める。 (本当は p 解法 上では p! / p^k * (p-k)! と書きま…

Codeforces Round #369 (Div. 2) Directed Roads

問題 codeforces.comn 個の頂点からなるグラフが与えられる。各頂点 i から, A[i] への有向グラフが一本ずつ生えている。このグラフの辺の向きをいくつか入れ替えることにより, このグラフにサイクルができないようにしたい(つまり x0 -> x1 -> ... -> xm ->…