11291: 【原1291】heaps

题目

题目描述

author: 王立力 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1291

Description

简单的描述往往意味着简单的题目。给定n个两两不同的数，用它们可以组成多少个不同的大小为n的堆？

提示：大根堆和小根堆都要考虑哦。

因为结果非常大，所以最后输出答案mod 1000000007的值即可。

Input Format

一个整数n

30%的数据n<=10

100%的数据n<=1000

Output Format

一行输出答案

Sample Input

3

Sample Output

4

zqy2018's solution

/*
    Hint: use combinatorics
*/
#include <bits/stdc++.h>
#define INF 2000000000
#define M 1000000007
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, f[1005] = {0}, C[1005][1005] = {0};
void init(){
    n = read();
    C[0][0] = 1;
    for (int i = 1; i <= n; ++i){
        C[i][0] = 1;
        for (int j = 1; j <= i; ++j)
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % M;
    }
}
void solve(){
    if (n <= 1) {
        printf("%d\n", n);
        return ;
    }
    f[1] = f[2] = 1;
    for (int i = 3; i <= n; ++i){
        int tt = 2;
        while (tt - 1 <= i)
            tt <<= 1;
        tt >>= 1;
        int lsize = min(tt >> 1, i - tt + 1);
        lsize += (tt - 1) >> 1;
        f[i] = 1ll * (C[i - 1][lsize]) * f[lsize] % M,
        f[i] = 1ll * f[i] * f[i - lsize - 1] % M;
    }
    int ans = 2ll * f[n] % M;
    printf("%d\n", ans);
}
int main(){
    init();
    solve();
    return 0;
}