minheap.java

第四届百度杯编程大赛final解题报告+标程

import java.util.*;

public class minHeap {
	
	public static final int maxSize	=	1000 + 10;
	public static int f[]	=	new	int[maxSize];
	public static int c[][] =	new int[maxSize][maxSize];
	
	public static void  main(String[] args)  {
	    Scanner cin = new Scanner(System.in);
	    int testNum;
	    testNum = cin.nextInt();
	    while (testNum -- > 0) {
	    	int n = cin.nextInt();
	    	int p = cin.nextInt();
	    	for (int i = 0; i <= 1000; i ++)
		        c[i][i] = c[i][0] = 1;
		    for (int i = 2; i <= 1000; i ++)
		        for (int j = 1; j < i; j ++)
		            c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % p;
		    
		    f[0] = f[1] = 1;
		    for (int i = 2; i <= 1000; i ++)
                    {
                            int t = 1;
                            while (t <= i) t = t * 2 + 1;
                            t = (t - 1) / 2;
                            t = (t - 1) / 2;
                            int right = t;
                            int left = i - 1 - t;
                            if (left > 2 * t + 1) {
                                    left = 2 * t + 1;
                                    right = i - 1 - left;
                            }
                            f[i] = (int) (((long) f[left] * c[i - 1][left]) % p);
                            f[i] = (int) (((long) f[i] * f[right]) % p);
                    }
	    	System.out.println(f[n]);
	    }
	}
}