コード
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
private long[] fibo;
public void solve() {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
long k = sc.nextLong();
sc.close();
fibo = new long[N + 1];
fibo[0] = 1;
fibo[1] = 1;
for (int i = 2; i <= N; i++) {
fibo[i] = fibo[i - 1] + fibo[i - 2];
}
ArrayList<Integer> list = fiboDFS(N, new ArrayList<Integer>(), k, 0);
for (Integer integer : list) {
System.out.print(integer + " ");
}
System.out.println();
}
private ArrayList<Integer> fiboDFS(int n, ArrayList<Integer> list, long k, int depth) {
if (n < 1) {
return list;
}
if (fibo[n - 1] < k) {
k -= fibo[n - 1];
list.add(2 + depth);
list.add(1 + depth);
return fiboDFS(n - 2, list, k, depth + 2);
} else {
list.add(1 + depth);
return fiboDFS(n - 1, list, k, depth + 1);
}
}
public static void main(String[] args) {
new Main().solve();
}
}
