CATALAN - Dãy số Catalan
Tác giả: khuc_tuan
Ngôn ngữ: Java
import java.io.*;
import java.util.*;
import java.math.*;
import static java.lang.Integer.parseInt;
class Process {
BigInteger[][] f;
public void run(int n, int[] a, BigInteger b) {
f=new BigInteger[2*n+1][2*n+1];
f[2*n][0] = BigInteger.valueOf(1);
for(int i=1;i<f[2*n].length;++i) f[2*n][i] = BigInteger.ZERO;
for(int i=2*n-1;i>=0;--i) {
for(int j=0;j<f[i].length;++j) {
f[i][j] = BigInteger.ZERO;
if(j>0) f[i][j] = f[i][j].add(f[i+1][j-1]);
if(j<f[i].length-1) f[i][j] = f[i][j].add(f[i+1][j+1]);
}
}
BigInteger c=BigInteger.ONE;
for(int i=1;i<2*n;++i) {
if(a[i]-2>=0 && a[i-1]<a[i]) c=c.add(f[i][a[i]-2]);
}
System.out.println(c);
int[] r=new int[2*n+1];
r[1]=1;
for(int i=2;i<2*n;++i) {
if( r[i-1]-1>=0) {
if(b.compareTo(f[i][r[i-1]-1]) > 0) {
b=b.subtract(f[i][r[i-1]-1]);
r[i]=r[i-1]+1;
}
else {
r[i]=r[i-1]-1;
}
}
else {
r[i]=r[i-1]+1;
}
}
for(int i=0;i<r.length;++i) { System.out.print(r[i]); System.out.print(' '); }
System.out.println();
}
}
public class Main {
public static void main(String[] Args) throws Exception {
BufferedReader kb=new BufferedReader(new InputStreamReader(System.in));
int n = parseInt(kb.readLine());
StringTokenizer st=new StringTokenizer(kb.readLine());
int[] a=new int[2*n+1];
for(int i=0;i<a.length;++i) a[i]=parseInt(st.nextToken());
BigInteger b=new BigInteger(kb.readLine());
new Process().run(n,a,b);
}
}