Pinary

原题：Pinary 1350

原题大意

Pinary数是一个仅由0和1组成的数，这个数不存在前导0，且相邻位置不能同时为1.
Pinary数的大小由长度和字典序决定，长度不同时，长度越小值越小，长度相同时，字典序越小值越小。
例如1是1，10是2，100,101,1000分别为3，4，5。
现在给出一个K，问这个数的Pinary表示形式是什么。

算法分析

先打表
solve(1) = 1;
sovle(10) = 2;
solve(100) = 3;
solve(1000) = 5;
solve(10000) = 8;
于是这个问题，就转换成了，将一个数字，拆成不连续的fib的若干项之和。@Zeckendorf 齐肯多夫定理。

程序代码

#include <iostream>
#include <vector>
using namespace std;
typedef long long LL;
int T, n, ans[102];
LL fib[102];
void init() {
    fib[1] = 1, fib[2] = 2;
    for(int i=3;i<=60;i++) {
        fib[i] = fib[i-1] + fib[i-2];
    }
}
vector<int> v;
int main() {
    init();
    scanf("%d", &T);
    while(T --) {
        scanf("%d", &n);
        v.clear();
        for(int i=60;i>=1;i--) {
            if(fib[i] <= n) {
                n -= fib[i];
                v.push_back(i);
            }
        }
        for(int i=1;i<=100;i++) ans[i] = 0;
        for(int i=0;i<v.size();i++) {
            ans[v[i]] = 1;
        }
        for(int i=v[0];i>=1;i--) {
            printf("%d", ans[i]);
        }
        printf("\n");
    }
}