けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

行列累乗

AtCoder ABC 129 F - Takahashi's Basics in Education and Learning (600 点)

重たい。。。 でも例えば行列 に対して の計算を行列累乗に帰着させるテクニックは、蟻本中級編の行列累乗のところに載っていたりする。それを膨らませると みたいな計算も、行列累乗でできそうという気持ちには確かになるよね。。。(なったけど昨日間に合わ…

AOJ 2624 Graph Automata Player (AOJ-ICPC 550 点)

グラフに行列は付き物!!! 問題へのリンク 問題概要 頂点の有向グラフが与えられる。自己ループを含み得るが、多重辺は含まないことが保証される。 各頂点に 0 か 1 の値が割り振られている (が、その値がわからない)。以下の操作を 回行った後の各頂点の…

MUJIN 2018 H - タイル張り (1000 点)

コンテスト終了後に「もう少しで解けそうだったのに...」と言ったのんな。アレは嘘だったのん... 問題へのリンク 概要 H × W の盤面を白黒に塗り分ける方法のうち、白い部分を 1 × 2 の長方形のピースで隙間なく埋められるようなものは何通りあるか? (99824…

CS Academy 069 DIV2 E - The Wall

とにかく整理に苦労したけど、本番中に通せて嬉しかったん CSA 069 DIV2 E The Wall 図は N = 5 の場合である。 N 段の壁を作りたい。ただし、どのレンガも下にあるレンガが完成してからでないと積み上げられない。 N 段の積み上げる順番の総数はいくらか。1…