Day 118-Q4 | フィボナッチ進数（Zeckendorf表現）上の桁DP

問題

整数 $L, R, K$ が与えられる。$L$以上$R$以下の整数$n$のうち、$n$をゼッケンドルフ表現（隣接しないフィボナッチ数の和として一意に表す表現。$F_2=1,F_3=2,F_4=3,F_5=5,\dots$を用いる）したときに使われるフィボナッチ数の個数がちょうど$K$であるものの個数を求めよ。

入力形式

L R K

制約

$1 \le L \le R \le 10^{18}$

$0 \le K \le 87$

入出力例

入力例1

1 20 2

出力例1

$4=3{+}1,\ 6=5{+}1,\ 7=5{+}2,\ 9=8{+}1,\ 10=8{+}2,\ 11=8{+}3,\ 14=13{+}1,\ 15=13{+}2,\ 16=13{+}3,\ 18=13{+}5$ の10個。

概念図: フィボナッチ進数の桁とDP状態

ヒント（段階的開示）

ヒント1: 方向性

通常の10進数や2進数の桁DPと同じ発想を、フィボナッチ数を「桁の重み」として使う数体系（フィボナッチ進数）に応用できないか考える。ゼッケンドルフの定理により、全ての正整数は「隣接しない」フィボナッチ数の和として一意に表せることが知られている。

ヒント2: アプローチ

フィボナッチ数を大きい方から $F_m, F_{m-1}, \dots, F_2$ と並べ、各位置を0/1の「桁」とみなす。「隣接する2桁が同時に1にならない」という制約下で、0/1の桁列を大きい桁から順に確定させていく桁DPが構成できる。桁列の大小関係は数値の大小関係と一致するため、通常の桁DPと同じ「tight」の考え方がそのまま使える。あとは「直前の桁が1だったか」と「使った1の個数」を状態に加えるだけでよい。

ヒント3: 誘導（コード骨格）

# 1. F[2..m] を、F[m] > R を満たす最小のmまで生成
# 2. X のゼッケンドルフ表現(桁配列, 上位から)を貪欲法で求める関数を用意する
#    (大きい方のフィボナッチ数から、使えるなら使う、を繰り返す)
# 3. f(X) = 0以上X以下の整数でK個の1を持つものの個数、を桁DPで求める
#    状態: (桁位置, tightかどうか, 直前の桁が1か, これまでに使った1の個数)
#    遷移: 直前が1なら次の桁は0固定。tightなら現在の桁の値まで、そうでなければ0/1自由
# 4. 答え = f(R) - f(L-1)

模範解答 (Python)

import sys
from functools import lru_cache


def build_fibs(limit):
    F = [0, 0, 1, 2]
    while F[-1] <= limit:
        F.append(F[-1] + F[-2])
    return F


def zeckendorf_digits(X, F, m):
    digits = []
    rem = X
    for i in range(m, 1, -1):
        if F[i] <= rem:
            digits.append(1)
            rem -= F[i]
        else:
            digits.append(0)
    return digits


def count_le(X, K, F, m):
    if X < 0:
        return 0
    digits = zeckendorf_digits(X, F, m)
    n = len(digits)

    @lru_cache(maxsize=None)
    def dp(pos, tight, prev1, ones):
        if ones > K:
            return 0
        if pos == n:
            return 1 if ones == K else 0
        limit = digits[pos] if tight else 1
        total = 0
        for d in range(0, limit + 1):
            if d == 1 and prev1:
                continue
            ntight = tight and (d == limit)
            total += dp(pos + 1, ntight, d == 1, ones + d)
        return total

    res = dp(0, True, False, 0)
    dp.cache_clear()
    return res


def solve():
    L, R, K = map(int, sys.stdin.readline().split())
    F = build_fibs(R + 10)
    m = len(F) - 1
    print(count_le(R, K, F, m) - count_le(L - 1, K, F, m))


solve()

計算量: フィボナッチ数は$O(\log_\varphi N)$個($N\le10^{18}$で約87個)しかないため、桁DPの状態数は「桁数×2(tight)×2(prev1)×K」程度で、全体で$O(\log N \times K)$。乱択200ケース（L,R,K）でゼッケンドルフ表現を素直に数え上げるブルートフォースと比較し、全て一致することを確認済み。

Step-by-Step 解説

1ゼッケンドルフの定理
任意の正整数は隣接しないフィボナッチ数の和として一意に表せる。この性質により「フィボナッチ進数」という一種の位取り記数法が定義できる。

2貪欲法による変換
大きいフィボナッチ数から順に「使えるなら使う」を繰り返すと、常に正しいゼッケンドルフ表現が得られる（$F_2+F_3+\dots+F_{k}

3桁DPへの応用
フィボナッチ進数の桁列は、通常の2進数と同じように「上位桁から見た大小関係＝数値の大小関係」という性質を持つため、桁DPの「tight」の考え方がそのまま流用できる。

4「隣接しない」制約の扱い方
直前の桁が1だった場合、次の桁は強制的に0にする、という遷移制約を1つ加えるだけで済む。

5計算量の確認
フィボナッチ数の個数は$O(\log N)$個しかないため、桁DPは非常に高速に動作する。

よくあるミス

ミス	原因	正しい書き方
フィボナッチ数列の始まりを$F_1{=}1,F_2{=}1$の重複ありで使ってしまう	ゼッケンドルフ表現では$F_1$を除いた非重複列を使う必要があることを見落とす	`F=[0,0,1,2]`から始めて重複しない列を明示的に構築する
$L{-}1$の計算で$L{=}1$のとき$X{=}0$を正しく扱えていない	0のゼッケンドルフ表現（空）を特別扱いし忘れる	`X<0`のときは0を返すようにし、$X{=}0$は「桁が全て0」として自然に処理させる
桁DPのメモ化キャッシュをKごとにクリアし忘れる	複数回count_leを呼ぶ際にlru_cacheが前回のKの結果を再利用してしまう	関数内でローカルにdpを定義し、呼び出しごとにcache_clear()する
桁列の大小比較がフィボナッチ進数でも通常の2進数と同じだと無条件に信じてしまう	直感的な類推だけで済ませ検証しない	ブルートフォースで小さいNの範囲について実際に突き合わせて確認する

次のステップ

発展: 「Kが偶数」のような条件や、「連続する0の個数がちょうど$m$個の位置がある」といった条件に拡張してみる。
次回予告: 木分解上の動的計画法（Tree Decomposition DP）

自己評価

完全理解おおむね理解要復習

Day 118-Q4 — フィボナッチ進数（Zeckendorf表現）上の桁DP

問題