TDPC - T フィボナッチ
まだ解いてなくて自分で解きたかったりしませんか大丈夫ですか救ってもらってもいいですか解法書きますよ大丈夫ですかではいきます
【追記】上の文字がおかしく見えるひとは違う世界に住んでいます
h1を文字大きくするためだけに使うのはやめようねSEOが死にますよ
TDPC - T フィボナッチ
覗いたらやってみたくなったのでやってみたら一苦労。
きたまさ法というのを使います。蟻本作者由来のアルゴリズムらしいですね。
蟻本の最後の「こんなアルゴリズムもあるよ」にも乗っているらしいですね。らしい、というのは椅子から動きたくないからです。
意味不明な記事がおおかった
僕の頭が足りないのでしょうが、「あーここの記事の通り式変形してこれをfとおけば自明で、典型なので〜」みたいな記事で、（いやほかのTDPCの問題の記事は良かったんですが、）
そんなんいいから、いい記事置いときます
m項間漸化式の高速なアルゴリズム
バタ子(btk)という方の記事です
ここ見ながらノート作れば完璧です。
完璧ですが、最後の
x_u = Σ(i=1, m) s_i × x_i
x_v = Σ(i=1, m) t_j × x_j
ならば
x_(u+v) = Σ(i=1, m) Σ(i=1, m) s_i × t_j × x_(i + j)
になる
というのが少し苦しみました
あと、このTDPC-Tは上記記事(すなわちきたまさ法で解ける問題)の特殊ケースであるということを念頭においてください。このことは僕のコードにも詳しくコメントを入れました。
しかし上記の式はとても重要で、
x_uとx_vが求まればx_(u+v)がO(m^2)で求まることを意味しています
記事の後ろに解説書くので同じくハマった人がいたら助けになればなと。(MathJaxとか知らない！)
Typical DP Contest : T - フィボナッチ
kmjpという方の記事
以下引用
yukicoderをちゃんとやっていれば余裕。
まとめには
yukicoderをやっていたら、TDPCの最終問題があっさり解けるようになっていた。
と。
yukicoderにきたまさ法を使える問題があるようです。
No.214 素数サイコロと合成数サイコロ (3-Medium)
No.215 素数サイコロと合成数サイコロ (3-Hard)
Easyもあります。
後者は高速きたまさ法というのを使うみたいです。
FFTがわからないので、JOIが終わった後にでもやろうと思います。
yukicoder強いですね、やっていこうとおもえました。
二つ目の記事ですが！
コードがとても綺麗です、さらっと最高にクールなテクを使っています
（一般的なんだろうなというか定義より明らかなんだけどさ！！数学の頭ないから！！）
まずnをディクリメントして、0-indexedで考えています。関係式は自分で0-indexedで求めなおしてください。
「ください。」ってなんだ。誰向けの記事だこれ。
あとまあ…さっき行ったようにx_0の係数のベクトルとx_1の係数のベクトルをまず用意しています
これが賢いなと思って、まああとはあの記事のコード見るなり、この記事のコード見るなり、コメントかツイッターで聞いてもらえればと思います。
x_(u+v)がもとまるとこについて
x_u = Σ(i=1, m) s_i × x_i … ①
x_v = Σ(i=1, m) t_j × x_j … ②
ならば
x_(u+v) = Σ(i=1, m) Σ(i=1, m) s_i × t_j × x_(i + j) … ③
美しいです。x_(2u)ももはやここから求まります
ということはx_(2u)を求める過程と似ています
やります
①と記事の前提2より
x_(u + v) = Σ(i=1, m) s_i × x_(i + v) … ④
②と記事の前提2より
x_(v + i) = Σ(j=1, m) t_j × x_(v + j) … ⑤
④に⑤を代入すれば③が求まります
やってみると案外自明ですね（この発想は危険で、理解した後全て自明に見えるのは当然）（というか理解したんですかね）
や、正直前提2.が前提1.からどうやって導かれるかわかるようなわからないような（あのあの）
おそらく入力の定義を当てはめれば数学的帰納法で証明可能とかだろう、今度する
感想
まだTDPC埋め終わってないのでうーん
はむこさんという方の解法を見たのですが、
berlekampMasseyとか書いててよくわからないのですが、
coeffs(mathworks)と書いてあったりして、これは「多項式の係数」を意味するようで、これはきたまさ法なのかな？と思ったりしていますが真偽は闇の中（聞いてみます）
以下コード抜粋
// 係数を表す列 x = {x_1, ... , x_k} と y = {y_1, ... , y_k}
// これはそれぞれ aの何項目かを表している
// 具体的には、a_i = A * x // 行ベクトル × 列ベクトル
// 今回は1<=i<=kについて A_i = 1
// (aの最初のk項についてさらに初項と呼んでいるブログがあったのでこう書いた)
// (これは罠で最初のk項で決定される列ベクトルが初項と呼ばれていたが、これがA)
// a_i = (xの総和)となるようなa_iを表現している
// yについても同様にa_i = (yの総和)となるようなa_iを表現
// この表現を保ったまま計算をしていくと、
// xとyがそれぞれa_u, a_vを表現しているとすると
// a_(u+v) = Σ(i=1, k) Σ(j=1, k) x_i * y_j * a_(i+j)
// と結構美しい感じになって、a_(u+v)をまた長さkのベクトルで表現して
// 計算していくのがきたまさ法ですよ
// なお、以下はすべて0-indexedであるが、0-indexedで計算し直すと以下の漸化式が出たのでok
VL mul(VL x, VL y) {
VL res(k*2, 0);
// 0-indexedであることに注意
REP(i, k) REP(j, k) (res[i+j] += x[i] * y[j] % MOD) %= MOD;
// k*2の長さがあるので、漸化式よりkの長さのベクトルで等価なものを求める
RFOR(i, k, k*2-1) {
REP(j, k) {
(res[i - j - 1] += res[i]) %= MOD;
// より一般にres[i] * c[k-1-j](=1)である
// cはx,yとは関係なく、漸化式(遷移式)に基づくものである
// (x,yはcに依存するが)
}
}
res.resize(k);
return res;
}
// きたまさ法
// O(k^2 log N)
int main() {
//#####//
if(n <= k) {
cout << 1 << endl; // より一般にa[n] (=1)
return 0;
}
VL tmp(k, 0), x(k, 0);
n--; // 0-indexedで考える
tmp[0] = 1; // x_0 を表現
x[1] = 1; // x_1 を表現
// 繰り返し自乗法
while(n>0) {
if(n&1) tmp = mul(tmp, x);
x = mul(x, x);
n>>=1;
}
// x_nが求まった
REP(i, k) ans += tmp[i]; // より一般にtmp[i] * a[i] (=1)
cout << ans%MOD << endl;
}
//一般的な場合との比較を意識して書いてみました。
マクロは感覚で読んで下さい。RFORは逆方向にFORします。
実装自体は２つ目に紹介した記事とほぼ同じです。
「表現」という表現は僕が勝手に言ってるだけです。
coeffsですね！（知らない）
つかれたー
