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

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

行列累乗

AtCoder ABC 178 D - Redistribution (緑色, 400 点)

総和が一定値になるような数列の数え上げ、最近よく見る! 問題へのリンク 問題概要 整数 が与えられる。 すべての項が 3 以上の整数で、その総和が であるような数列の個数を 1000000007 で割ったあまりを求めよ。 制約 解法 (1):素直に DP まずは素直な D…

AtCoder AGC 003 F - Fraction of Fractal (銅色, 1700 点)

頭がゴチャゴチャしてきて、詰め切るのがとても大変だった。 でも整理し切った後に出てくる性質は、至極単純なものだった。面白い。 問題へのリンク 問題概要 のグリッドが与えられ、各マスは白黒に塗られている。この盤面をレベル 1 のフラクタルとする。 …

AtCoder AGC 006 C - Rabbit Exercise (銅色, 800 点)

操作を 回行った結果を求める系、苦手意識あるけど克服したい! 問題へのリンク 問題概要 と番号の振られた 個のボールがあって、初期状態ではそれぞれ の位置にある。以下の操作を 回行う。最終的な各ボールの座標の期待値をそれぞれ求めよ。 各操作は 個の…

yukicoder No.980 Fibonacci Convolution Hard (母関数)

すごい面白かった!!! 問題へのリンク 問題概要 整数 が与えらえたときに、漸化式 を満たす数列 が与えられる。これに対して以下の 個のクエリに答えよ: 1 つのクエリは 2 以上の整数 が指定され、 を満たすような正の整数 に対して、 の総和を求め、10000…

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…