URAL 1081

題目大意：求詞典序下第K個長度為N且無相鄰位置都為1的0、1序列。無解時輸出-1。

例如：

input:     output:

3 1        000(所有符合條件的序列有：000，001，010，100，101)

Time Limit:500MS     Memory Limit:65536KB     64bit IO Format:%I64d & %I64u

數據規模：0<N<44,0<K<10^9。

理論基礎：無。

題目分析：先觀察：1-5位的答案。

1:01

2:00 01 10

3:000 001 010100 101

4:00000001 00100100 01011000 10011010

5:0000000001 00010 00100 0010101000 0100101010 10000 10001 10010 1010010101

觀察數目：1:2,2:3,3:5,4:8,5:13...這是巧合嗎？不是。我們看新序列的生成方式。在n-1位的所有序列的最高位添加0，數目為ans[i-1]，在n-1位的所有最高位為0的序列前添加1,數目為ans[i-2]（為什麼呢？想想最高位為0的序列都是怎麼來的？？？）這樣，我們就得出：ans[i]=ans[i-1]+ans[i-2]。可是要的不是數目啊，是第K個序列啊。。。好吧，狀態壓縮dp可以解決，但是有沒有更簡單的方法呢？

我們再來觀察：當N=5，K<=ans[4]時，我們輸出的最高位肯定是0，這時只需要輸出ans[4]時的K不就行了？同樣此時如果K<=ans[3]遞推下去。那如果K>ans[3]呢？那我們肯定輸出的最高位是1，這時只需要輸出ans[3]時的K-ans[3]不就行了？問題得到解決。。。

代碼如下：

 
#include<iostream>   
#include<cstring>   
#include<string>   
#include<cstdlib>   
#include<cstdio>   
#include<cmath>   
#include<algorithm>   
#include<queue>   
#include<ctime>   
#include<vector>   
using namespace std;  
typedef double db;  
#define DBG 0   
#define maa (1<<31)   
#define mii ((1<<31)-1)   
#define ast(b) if(DBG && !(b)) { printf("%d!!|\n", __LINE__); while(1) getchar(); }  //調試   
#define dout DBG && cout << __LINE__ << ">>| "   
#define pr(x) #x"=" << (x) << " | "   
#define mk(x) DBG && cout << __LINE__ << "**| "#x << endl   
#define pra(arr, a, b)  if(DBG) {\   
    dout<<#arr"[] |" <<endl; \  
    for(int i=a,i_b=b;i<=i_b;i++) cout<<"["<<i<<"]="<<arr[i]<<" |"<<((i-(a)+1)%8?" ":"\n"); \  
    if((b-a+1)%8) puts("");\  
}  
template<class T> inline bool updateMin(T& a, T b) { return a>b? a=b, true: false; }  
template<class T> inline bool updateMax(T& a, T b) { return a<b? a=b, true: false; }  
typedef long long LL;  
typedef long unsigned int LU;  
typedef long long unsigned int LLU;  
#define N 43   
int Fibonacci[N+1]={1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,  
2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,  
832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,  
63245986,102334155,165580141,267914296,433494437,701408733,1134903170};  
int n,k;  
int main()  
{  
    while(~scanf("%d%d",&n,&k))  
    {  
        if(k>Fibonacci[n])  
        {  
            puts("-1");  
            continue;  
        }  
        while(n)  
        {  
            if(k<=Fibonacci[--n])printf("0");  
            else  
            {  
                printf("1");  
                k-=Fibonacci[n];  
            }  
        }  
        puts("");  
    }  
    return 0;  
}