Project Euler - Problem 297

Zeckendorf Representation

Problem 297 (日本語訳)

フィボナッチ数列の各項は前の2つの項を足して生成される.
1 と 2 から始めて, 最初の 10 項は: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 である.

全ての正整数はフィボナッチ数列の連続しない項の合計で一意に表せる. 例えば, 100 = 3 + 8 + 89 である.
そのような合計はゼッケンドルフ表記(Zeckendorf representation)と呼ばれる.

整数 n>0 に対し, z(n) を n のゼッケンドルフ表記中の項数とする.
つまり z(5) = 1, z(14) = 2, z(100) = 3 となる.
また, 0<n<10⁶ に対し, Σz(n) = 7894453 である.
0<n<10¹⁷ に対し Σz(n) を求めよ.

(日本語訳より)

こんな感じの表を書きなぐっていると赤い部分とかに繰り返し構造があり

$dp[n] = \sum_{i = 0}^{n - 1} z(n) $

として，以下の漸化式が生えてくる

$dp[1] = 0$
$dp[N] = dp[a_{k}] + dp[N - a_{k}] + (N - a_{k})$

ただし，a_k は N 未満の最大のフィボナッチ数

map でメモ化再帰すると爆発することなくすぐ答えがでる

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;


const int LIM = 90;
ll fib[LIM];

map<ll, ll> dp;

ll zsum(ll N) {
    if (dp.find(N) != dp.end()) return dp[N];
    if (N == 1) return (dp[1] = 0);
    // N 未満で最大のフィボナッチ数を求める
    int i;
    for (i = 0; fib[i + 1] < N; i++);
    return (dp[N] = (N - fib[i]) + zsum(fib[i]) + zsum(N - fib[i]));
}

int main()
{
    clock_t start, end;
    start = clock();

    //cin.tie(0);
    //ios::sync_with_stdio(false);

    // fibonacci
    fib[1] = 1; fib[2] = 2;
    for (int i = 3; i < LIM; i++) fib[i] = fib[i - 1] + fib[i - 2];

    const ll N = 100000000000000000LL;
    cout << zsum(N) << endl;

    end = clock();
    printf("%d msec.\n", end - start);

    return 0;
}

1 msec 以内