This is a difficult one.

First. If we have a method “solve”, given some fixed digits and given some undetermined digits in the array, we know how many distinct beads combinations there are, we can have this skeleton algorithm:

#include <iostream> #include <vector> #include <list> #include <map> #include <unordered_map> #include <algorithm> #include <string> #include <memory> #include <cstring> using namespace std; #include <stdio.h> #include <stdlib.h> int n, k; int a[55]; long long c[55][55][2][2]; bool visited[55][55][2][2]; int main() { cin >> n >> k; k++; // because 0000000..000 doesn't count memset(a, -1, sizeof(a)); a[0] = 0; //first one must 0. if (solve(0, n - 1, 0, 0) < k) { cout << -1 << endl; return 0; } for (int i = 1; i < n; ++i) { memset(visited, 0, sizeof(visited)); a[i] = 0; if (k > solve(0, n - 1, 0, 0)) { k -= solve(0, n - 1, 0, 0); //remove all a[i] == 0 possibilities. a[i] = 1; //so it has to be 1. } } for (int i = 0; i<n; i++) { cout << a[i]; } cout << endl; return 0; }

The way to implement solve() is based on following critical observations:

- We want to know how many groups there are, i.e. how many smallest numbers – i.e. how many numbers will not become smaller if transformed by 3 operations: revert, invert or revert+invert.
- Reduce and conquer: each time we enumerate the left-end and right-end of current range of array. Then reduce the size of the problem by 2.
- 0….1 can always be used when enumerating. Because it cannot be made smaller by any of the 3 operations.
- 0….0 can always be used.
- If there is an outer 0…1, then 1…0 can be used in following enumerations. i.e. 0…1….0…1 because any operation cannot make the number smaller. (yes i know it’s related to 0…0 and 1…1 placements but you will understand if you are patient. also this is not a complete proof. you will need to do induction if you want one.)
- If there is an outer 0…0, then 1…1 can be used. i.e. 0…1…1…0
- If we make sure 1…1 is always enclosed by some 0…0, and 1…0 is always enclosed by some 0…1, then the result number is a smaller number in some group. (and all such numbers meet this condition.)
- So we have the following implementation of solve() function

long long solve(int l, int r, int can10, int can11) { //if there has been 0---0, we can start to put 1---1 because rev-inv will make a larger number. (0---1 and 1---0 keep same) //if there has been 0---1, we can start to put 1---0 because rev will make a larger number. (0---0 and 1---1 keep same) if (l > r) { return 1; } if (visited[l][r][can10][can11]) { return c[l][r][can10][can11]; } visited[l][r][can10][can11] = true; long long& ans = c[l][r][can10][can11]; ans = 0; for (int nl = 0; nl < 2; ++nl) { if (a[l] != -1 && a[l] != nl) { //already fixed. continue; } for (int nr = 0; nr < 2; ++nr) { if (a[r] != -1 && a[r] != nr) { //already fixed. continue; } if (!can10 && nl > nr) { continue; } if (!can11 && nl && nr) { continue; } if (l == r && nl != nr) { continue; } ans += solve(l + 1, r - 1, can10 || nl < nr, can11 || (!nl && !nr)); } } return ans; }