フィボナッチ数列の計算(メモ化再帰のテンプレートとしても使える)
#include <bits/stdc++.h> namespace NyaaLIB { struct ARG_MF { using ll = long long; using vl = std::vector<ll>; ll n; vl& memo; }; auto XXL_MF = [&](auto self, ARG_MF a) -> void { if (a.n <= 2) { // 末端が計算済でないなら計算 a.memo[1] = a.memo[2] = 1; return; } // 未計算なら潜る if (a.memo[a.n - 1] == 0) self(self, { a.n - 1, a.memo }); // メモを使って計算 a.memo[a.n] = a.memo[a.n - 1] + a.memo[a.n - 2]; }; }
how to use
int main() { std::vector<long long> memo(11); NyaaLIB::XXL_MF(XXL_MF, { 10, memo }); for (auto& e : memo) cout << e << " "; return 0; }
0 1 1 2 3 5 8 13 21 34 55
実装例
https://atcoder.jp/contests/abc079/submissions/31112202
https://atcoder.jp/contests/abc247/submissions/31112557