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);
	}
}

Download