7K12 blog

猫でも分かるアルゴリズム解説

NyaaLIB::XXL_MF

フィボナッチ数列の計算(メモ化再帰のテンプレートとしても使える)

#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