drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ AtCoder AtCoder1700点 AGC-F フラクタル構造 再帰的構造に着目する 行列 行列累乗 係数を考える 連結成分 二次元グリッド 数え上げ問題 考察：場合分けして考える ダブリング 数学的帰納法に基づく考察 複雑度がlogオーダー 銅色diff NoviSteps4D 頭がゴチャゴチャしてきて、詰め切るのがとても大変だった。 でも整理し切った後に出てくる性質は、至極単純なものだった。面白い。 問題へのリンク 問題概要 のグリッドが与えられ、各マスは白黒に塗られている。この盤面をレベル 1 のフラクタルとする。 レベル のフラクタルとは黒いマスひとつからなる のグリッド レベル のフラクタルとは、レベル のフラクタルを、グリッドの全ての黒いマスに相当する位置に並べ、白いマスに相当する位置は白いマスで埋めたもの レベル のフラクタルにおいて黒マスからなる連結成分の個数が何個あるか、1000000007 で割ったあまりを求めよ。 制約 考えたこと たとえば ...… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2020%2F03%2F08%2F175100" title="AtCoder AGC 003 F - Fraction of Fractal (4D, 銅色, 1700 点) - けんちょんの競プロ精進記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.user.blog.st-hatena.com/default_entry_og_image/80936665/1687765056723440 Hatena Blog https://hatena.blog 2020-03-08 17:51:00 rich https://drken1215.hatenablog.com/entry/2020/03/08/175100 1.0 100%