square869120Contest #3: G - フィボナッチ数の総和

http://s8pc-3.contest.atcoder.jp/tasks/s8pc_3_g

解法

キーになるのは次の性質。

$$ F_{1}+F_{2}+\cdots+F_{n}=F_{n+2}-1 $$

この性質を用いて2段目を埋めてみる。

加法の線形性（重ね合わせの理）を考えると、上の表は次の2つの表に分解して、それぞれで (n,m) が何になるかを求めて足せばいいことが分かる。

-1が並んでいる方の表を考えてみよう。

(2,1)のセルに-1が書き込まれており、それ以外が0だったとする。このとき、(5,7)のセルに書き込まれる値は、下図の最短経路数×(-1)になる。

(2,2)のセルに-1が書き込まれており、それ以外が0だったとする。このとき、(5,7)のセルに書き込まれる値は、下図の最短経路数×(-1)になる。

結局のところ、2行目が全部-1で埋まっていれば、(5,7)のセルに書き込まれる値は、下図の最短経路数×(-1)になる。

全部作業を終えると次のような表が得られる。次の段に移動するたびに誤差項が出てくるので、そのたび重ね合わせの理で表外に追い出す。追い出した値が(5,7)に与える影響を非フィボナッチ項の列に書いた。

二項係数の値は以下の関係式を使えば順次求められる。割り算をするので逆元が存在しないと怖いが、今回は大丈夫。

$$ \binom{n+1}{r+1}=\frac{n+1}{r+1}\binom{n}{r} $$

---

1..nの逆元のテーブルをO(n)で作るテクニックというのが存在する。除算のよくある関係式を使う。

$$ M = (M/i)i + (M \% i) $$

mod M の世界では、

$$ 0 = (M/i)i + (M \% i) $$

なので、

$$ 0 = (M/i) + (M \% i)i^{-1} $$ $$ i^{-1} = -(M/i)(M \% i)^{-1}$$

が成り立つ。これは結構便利。

F1+...+Fn=F[n+2]-1、言われてみればそうなんだけど、以外と気付かない。