A一完でした。
コンテスト後のツイート
yukicoder contest 336 AのみAC
— titia (@titia_til) March 18, 2022
A 頂点数3以上のサイクルに分ける。DP
C 偶数ならフィボナッチだけど、奇数ならフィボナッチ数の積の和になるから、畳み込みとか使うのか？ と悩んでいた。他の方のツイート見ると、こっちもDP（→行列累乗）できるみたいね。
No.1879 How many matchings?
上記ツイートの通りで、奇数の場合もDPでいけるということをヒントにしてAC。
偶数のときにDPになることには気付いていたのだから、奇数の場合も同じ方針で立式、遷移を書いてみるべきだった。
0 件のコメント:
コメントを投稿