https://csacademy.com/contest/ceoi-2018-day-2/task/fibonacci-representations-big/problemFibonacci数列$F$を考える。正整数$p$に対し$X(p)$を、$p$を互いに異なるfibonacci数の和として表現する方法の数とする。a_n$が与えられる。solutionFibonacci数の和をZeckendorfの表現してこれに沿ってDP。普通にDPを毎回やり直すと$O(n)$かかるので行列を動的構築segment木に乗せる。正整数$p$のFibonacci数の和による表現で正規なものを考えてみよう。後のことを考えると大きいものから貪欲に使っていった場合の形で保持するのが正解。その更新は悪意がない限りほぼ定数時間。部分点ならここまでで十分で、愚直な再帰を書けばよい。いうのがあるので満点にはならない。これを解決したいならそのような区間の集合を管理すればよい。$p$のZeckendorfの表現があるときに$X(p)$を求めたい。これは小さい方からのDPで求まる。再帰的に展開でき、かつひとつ下の項に邪魔されて止まるので、ひとつ下の項との距離にほぼ比例する数だけ$X(p)$が大きくなる。その差分の偶奇によっては厄介で、ひとつ下の項が展開されたかされてないかで場合分けが必要。j)$というDPで求まる。見做せかつ線形なので、この形でなら好きな順序で更新できる。2$行列の積を取っていることになる。これを動的構築segment木に乗せれば終了。r)$に対応した行列を位置$l$や位置$r$に置くことになる。noteコーナーに気付かず実装して投げたらTLEし、部分点でさえ実装は面倒だったのに捨ててさらに面倒なのを書く気力がなくて終了。満点には切断結合のできる平衡二分木の上で遅延評価をしないとだめだと思ってたのも一因。コンテスト終了後に次を見て現実的な実装量だと気付いたので頑張って書きました。ゼッケンドルフの表現で表す方法を考える。「1こ飛ばしで使われる区間」の集合を管理すると良い。2018年8月16日そこから答えを求めるためには、それぞれの区間について定まる2x2行列の積を取れば良い。行列は自分と隣の区間にしか寄らないので、集合を更新するときに処理すれば計算量は抑えら得られる。2018年8月16日Zeckendorfの表現というのは知らなかった。やる発想も知らなかった。構築時に右端を決め打ちする必要がある。