WARushスマートフォン用の表示で見るWARushSRMの結果とか、解けた問題のコードを書いていきますこの広告は、90日以上更新していないブログに表示しています。今日、ボブは奇妙なグラフの塗り分けを数えることに挑戦している。そのグラフは小さな輪が繋がって大きな輪を作っている。グラフは実線と点線の、2つのタイプのエッジを持つ。小さな輪を形作るエッジは全て実線である。大きな輪を形作るエッジは全て点線である。正確には、そのグラフはN個の輪を持つ。C_N-1と順番に番号が付けられている。vertexCountが与えられる。C_iはvertexCount[i]だけの頂点を持つ。v_i_vertexCount[i]-1と順番に番号が付けられている。輪であるため、最後の頂点は最初の頂点と繋がることに注意して欲しい。これらは全て実線のエッジで繋がっている。toVertexが与えられる。これらはC_iとC_i+1が次のように繋がっていることを表す。C_iの頂点v_i_fromVertex[i]とC_i+1の頂点v_i+1_toVertex[i]は、点線のエッジによって繋がっている。ボブはK色で、このグラフを下記のルールに従い色を塗るときに、何パターン塗り分けることができるかを知りたい。実線で繋がっている頂点は違う色で塗らなくてはならない。点線で繋がっている頂点は同じ色で塗らなくてはならない。色の塗り分けのパターン数を返せ。10^9解法それぞれの小さな輪において、fromとtoが同じ色で塗られたときのパターン数と、違う色で塗られたときのパターン数をDPでだす。小さな輪の頂点は全て実線で繋がっているため、前の頂点と同じにならないように色を塗っていく。2)次に、大きな輪において、toの頂点が0番目の輪のfromと同じ色で塗られたときのパターン数と、違う色で塗られたときのパターン数をDPする。"ABBADiv1"月別アーカイブリンクはてなブログブログをはじめる(無料)お知らせはてなブログをはじめよう!Ekaingさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。