minheap.cpp

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

/**********************************************************************
Author: Felicia
Created Time:  2009-2-19 14:13:28
File Name: whu09_3.cpp
Description: 
**********************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long int64;
const int maxint = 0x7FFFFFFF;
const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;

const int maxn = 1010;
int M;

int c[maxn][maxn];
int f[maxn];

void calc_c() {
    for (int i = 0; i < maxn; i++) {
        c[i][0] = c[i][i] = 1;
        for (int j = 1; j < i; j++) {
            c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % M;
        }
    }
}

int dp(int n, int depth) {
    if (f[n] != -1)
        return f[n];
    if (n == 1 || n == 0)
        return 1;
    int t = 1;
    while (t <= n) t = t * 2 + 1;
    t = (t - 1) / 2;
    t = (t - 1) / 2;
    int right = t;
    int left = n - 1 - t;
    if (left > 2 * t + 1) {
        left = 2 * t + 1;
        right = n - 1 - left;
    }

    return f[n] = (long long)dp(left, depth+1) * dp(right, depth+1) % M * (long long)c[n - 1][left] % M;
}

int main() {
    int n;
    int ca;
    scanf("%d", &ca);
    for (int t = 0; t < ca; t++) {
        scanf("%d%d", &n, &M);
        memset(c, 0, sizeof(c));
        calc_c();
        memset(f, -1, sizeof(f));
        printf("%d\n", dp(n, 0));
    }
    return 0;
}