CF Beta Round 93-D.Fibonacci Sums-齐肯多夫分解、DP
https://codeforces.com/contest/126/problem/D
定义Fibonacci序列：\(F_1=1,F_2=2,F_k=F_{k-1}+F_{k-2}(\forall k\geq 3)\)，给正整数 \(n(1\leq n\leq 10^{18})\)，问将 \(n\) 分解成若干不同的Fibonacci数有多少种方案。
Theorem (齐肯多夫 Zeckendorf 定理) 任何正整数都能表示为若干个不连续的斐波那契数之和。
证明. 存在性是显然的，关键在于说明不连续。归纳假设，首先结论对于 \(n = 1, 2\) 成立，现在假设结论对所有不超过 \(m\) 的正整数成立，尝试说明 \(m + 1\) 的情形：
- (1) 若 \(m + 1\) 是 Fibonacci 数，则结论显然成立。
- (2) 否则，\(\exists n'\) s.t. \(F_{n'} < m + 1 < F_{n'+1}\)，令 \(m' = (m + 1) − F_{n'} \leq m + 1 − 1 ≤ m\)，根据归纳假设 \(m'\) 能被写成若干不连续 Fibonacci 数之和，设\(m′=F_{n_1} + \dots + F_{n_k}\)，其中 \(n_1<\dots<n_k\)，因 \(F_{n_k} \leq m' = (m+1)-F_{n'}< F_{n'+1} − F_{n'} = F_{n'−1}\)，即 \(F_{n_k}<F_{n'-1}\)，Fibonacci 序列有单调性，则 \(n_k < n'− 1\)，即\(n'\) 和 \(n_k\) 也不连续，且 \(n' > n_k > \dots > n_0\)。
因此全体正整数都可以按照Fibonacci序列分解，看成是一个无穷维的向量\(n\equiv (b_1,b_2,\dots,b_k,\dots)\)，其中 \(b_i\in \{0,1\}\) ，\(n=\sum b_i F_i\)，这样的表示不仅唯一，并且存在一种分解方式，使得：不存在 \(b_i,b_{i+1}\) 同时为 \(1\) ，我们把这种分解方式称为齐肯多夫Zeckendorf分解，上面的归纳告诉了我们要怎么做——从大到小检查Fibonacci序列就行了。
这样可以得到一个 \(O(\log n)\) 位的01序列，且没有相邻的1，那么怎么样拆分呢？
一旦出现“100”，总是可以拆成“011”，如果后面还有”00”，还能继续操作，即\(100 00\to 01100\to 01011\)，而如果是“101”的话，那第一个1其实是不能继续拆的，那么就考虑dp，设 \(f(i,0/1)\) 表示考虑分解中的第 \(i\) 位 1 是否拆解，如果要继续拆，那其实只能往一个方向拆，那么就只取决于两个 1 之间的距离：
所以可以写出
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define endl '\n'
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
const int N=100;
ll n,fib[N],f[N][2];
int main(){
fastio;
fib[1]=1;fib[2]=2;
int sz=2;
while(1){
sz++;
fib[sz]=fib[sz-1]+fib[sz-2];
if(fib[sz]>1e18)break;
}
int tc;cin>>tc;
while(tc--){
cin>>n;
vector<int> p;
for(int i=sz;i>=1;i--)if(fib[i]<=n){
p.push_back(i);
n-=fib[i];
}
reverse(p.begin(),p.end());
int mx=p.size();
f[0][0]=1;
f[0][1]=(p[0]-1)/2;
for(int i=1;i<mx;i++){
f[i][0]=f[i-1][0]+f[i-1][1];
f[i][1]=f[i-1][0]*((p[i]-p[i-1]-1)/2)+f[i-1][1]*((p[i]-p[i-1])/2);
}
cout<<f[mx-1][0]+f[mx-1][1]<<endl;
}
return 0;
}