One Martian boy called Zorg wants to present a string of beads to his friend from the Earth — Masha. He knows that Masha likes two colours: blue and red, — and right in the shop where he has come, there is a variety of adornments with beads of these two colours. All the strings of beads have a small fastener, and if one unfastens it, one might notice that all the strings of beads in the shop are of the same length. Because of the peculiarities of the Martian eyesight, if Zorg sees one blue-and-red string of beads first, and then the other with red beads instead of blue ones, and blue — instead of red, he regards these two strings of beads as identical. In other words, Zorg regards as identical not only those strings of beads that can be derived from each other by the string turnover, but as well those that can be derived from each other by a mutual replacement of colours and/or by the string turnover.
It is known that all Martians are very orderly, and if a Martian sees some amount of objects, he tries to put them in good order. Zorg thinks that a red bead is smaller than a blue one. Let's put 0 for a red bead, and 1 — for a blue one. From two strings the Martian puts earlier the string with a red bead in the i-th position, providing that the second string has a blue bead in the i-th position, and the first two beads i - 1 are identical.
At first Zorg unfastens all the strings of beads, and puts them into small heaps so, that in each heap strings are identical, in his opinion. Then he sorts out the heaps and chooses the minimum string in each heap, in his opinion. He gives the unnecassary strings back to the shop assistant and says he doesn't need them any more. Then Zorg sorts out the remaining strings of beads and buys the string with index k.
All these manupulations will take Zorg a lot of time, that's why he asks you to help and find the string of beads for Masha.
The input file contains two integers n and k (2 ≤ n ≤ 50;1 ≤ k ≤ 1016) —the length of a string of beads, and the index of the string, chosen by Zorg.
Output the k-th string of beads, putting 0 for a red bead, and 1 — for a blue one. If it s impossible to find the required string, output the only number -1.
4 4
0101
Let's consider the example of strings of length 4 — 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110. Zorg will divide them into heaps: {0001, 0111, 1000, 1110}, {0010, 0100, 1011, 1101}, {0011, 1100}, {0101, 1010}, {0110, 1001}. Then he will choose the minimum strings of beads in each heap: 0001, 0010, 0011, 0101, 0110. The forth string — 0101.
题意：将所有n位二进制串（允许前导0）中同时满足字典序不小于其逆序串、取反串和逆序取反串 的串提取出来，按字典序排序，求第m个。 n ≤ 50,k ≤ 1016
分析：好有趣的一道题，类似数位DP的方法,dp[i][limit1][limit2] 表示当前第i位(n-i+1位)，前缀是否等于逆序串前缀，前缀是否等于逆序反串前缀的方案数。但是怎么求第K个呢？我们可以一位一位来，将当前位为0的方案数计算出来，如果大于等于K那么当前为一定为0，否则将当前位填1然后K减去方案数，循环n位即可。
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<set>
#include<map>
#include<vector>
#include<cstring>
#include<stack>
#include<queue>
#define INF 0x3f3f3f3f
#define eps 1e-9
#define MOD 1000000007
#define MAXN 200005
using namespace std;
typedef long long ll;
ll n,k,a[55],dp[55][2][2];
ll dfs(int pos,int limit1,int limit2)
{
if(pos < n-pos+1) return 1ll;
if(dp[pos][limit1][limit2] >= 0) return dp[pos][limit1][limit2];
ll ans = 0;
for(int i = 0;i < 2;i++)
if(i == a[pos] || a[pos] == -1)
for(int j = 0;j < 2;j++)
if(j == a[n-pos+1] || a[n-pos+1] == -1)
if((!limit1 || i <= j) && (!limit2 || i <= !j) && (pos != n-pos+1 || i == j)) ans += dfs(pos-1,limit1 & (i == j),limit2 & (i != j));
dp[pos][limit1][limit2] = ans;
return ans;
}
int main()
{
memset(dp,-1,sizeof(dp));
memset(a,-1,sizeof(a));
cin>>n>>k;
k++;
a[n] = 0;
if(dfs(n,1,1) < k)
{
cout<<-1<<endl;
return 0;
}
cout<<0;
for(int i = n-1;i;i--)
{
a[i] = 0;
memset(dp,-1,sizeof(dp));
ll temp = dfs(n,1,1);
if(temp < k)
{
k -= temp;
a[i] = 1;
cout<<1;
}
else cout<<0;
}
}