Ural2004： Scientists from Spilkovo（德布鲁因序列&思维）

Misha and Dima are promising young scientists. They make incredible discoveries every day together with their colleagues in the Spilkovo innovative center. Now Misha and Dima are studying the properties of an amazing function F which is written as follows.

C++:

int F(int x, int n)
{
    return (((x & ((1 << (n / 2)) - 1)) << ((n + 1) / 2)) | (x >> (n / 2)));
}

Pascal:

function F(x, n: integer): integer;
begin
    F := (((x and ((1 shl (n div 2)) - 1)) shl ((n + 1) div 2)) or (x shr (n div 2)));
end;

The friends want to perform the following computational experiment.

All integers from 0 to 2n − 1 are written.
Each integer x is replaced by F(x, n).
Each integer obtained after step 2 is written as a binary string of length n (if the integer has less than n bits, some leading zeroes are added; if the integer has more than n bits, only last n bits are written).
The result of the experiment is a binary string of minimum length, that contains all the strings obtained after step 3 as its substrings.

If you can perform this experiment, maybe you are able to work in Spilkovo too!

Input

The only line contains an integer n (1 ≤ n ≤ 20).

Output

Output the required binary string. If there are several optimal solutions, you may output any of them.

Sample

input	output
1	10

Problem Author: Ilya Kuchumov

题意：给定N，那么对于长度为N的二进制串有2^N种（0,1,2....2^N-1），现在把这些串用二进制表示处理，不满N位的前面补0，现在希望找到最短的字符串S，使得这些二进制串全部是S的字串。

思路：首先题目有个翻转过程，但其实翻转之后这2^N个数依然是对应(0,1,2...2^N-1)，因为他们翻转前两两不同（至少有一位不同），翻转的时候按同样的规则翻转，所以翻转后也两两不同，所以值域不变。所以可以不考虑翻转过程了。然后考虑求S：

有个叫‘德布鲁因序列’的东西：和什么差不多也是包含了所有的字串，但是多一个有环的性质，其答案的长度是2^N；和它的证明相似，但是这里的S无环，所以长度是2^N+N-1。根据其性质，知道‘德布鲁因序列’的数量是阶乘级别的，说明我们暴力求S的话，需要回溯的次数不多，所以N<=20我暴力回溯求S问题不大。

这个‘德布鲁因序列’，我大概看了一下，有些复杂，日后再细看咯。参考：http://www.cocoachina.com/cms/wap.php?action=article&id=21098

事实证明，只花了100ms。。不过应该有更高效的方法。

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=2000000;
int vis[maxn],a[maxn],M,N;
bool dfs(int p,int num){
    if(p==M+1){
        for(int i=1;i<=M;i++) printf("%d",a[i]);
        cout<<endl;
        return true;
    }
    num&=((1<<(N-1))-1); num<<=1;    
    if(!vis[num]){
        vis[num]=1;
        a[p]=0;
        if(dfs(p+1,num)) return true;
        vis[num]=0;
     }
     if(!vis[num+1]){
         vis[num+1]=1;
         a[p]=1;
         if(dfs(p+1,num+1)) return true;
         vis[num+1]=0;
     }
     return false;
}
int main()
{
    cin>>N; M=pow(2,N)+N-1;
    vis[0]=1;  dfs(N+1,0);
    return 0;
}