ARC081 D Coloring Dominoes

所見

中 学 入 試
(1)
aab
ccb
(2)
aabd
ccbd
(3)
aabde
ccbde
(4)
RvvttdWIyyPPQFFZZssffEEkka
RLLwwdWIxxNNQUUXXVVMMooBBa
を塗り分ける場合の数を求めなさい
とかだとむちゃむちゃ中学入試っぽいと思います

問題概要

2*Nマスの範囲に1枚の面積が1マスのタイルが並べられた図形が与えられる。その図形を3色で塗り分けるときの場合の数を1000000007で割った余りを求めよ。

取った方針

タテ向きまたはヨコ向き*2のタイルを右端に追加した時増える場合の数は一つ左の状態でのみ定まる。具体的には、タテ向きのタイルの置き方を0、ヨコ向きのタイルの置き方を1とすると、
左が0:右に0を置いても1を置いても場合の数は2倍
左が1:右に0を置くと1倍、1を置くと3倍
となる。
あとはこれをmod取り構造体でシミュレーションすれば終了。(掛け算しかしないので構造体を使う必要はあまりない)

正しい方針(解説の方針)

同上

得られた知見

・i-1番目の情報からi番目の値が求まる、DP的な思考回路(DPではない)
・中学受験をしてから10年以上が経っているというつらい現実

解くのに必要な要素

・場合の数
・タイルを増やした時に増える場合の数はその左側のタイルの並びに依存するという気づき

周辺調査によって得られた知見

なし