Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

A binary search tree is a binary tree. It may be empty. If it is not empty, it satisfies the following properties:

(1)

Every node has a key, and no two nodes have the same key.

(2)

The keys in a nonempty left subtree must be smaller than the key in the root of the subtree.

(3)

The keys in a nonempty right subtree must be larger than the key in the root of the subtree.

(4)

The left and right subtrees are also binary search trees.

Sample binary search trees are shown in Figure 1.

To search for a node with a key k in a binary search tree T, we begin at the root. If T is empty, T contains no keys and the search is unsuccessful. Otherwise, we compare k with the key in root. If k equals root's key, then the search terminates successfully. If k is less than root's key, we search the left subtree of the root. If k is larger than root's key, we search the right subtree of the root. In the same way, we can proceed the search in the left or right subree of T.

To insert a new key k into a binary search tree T where k is different from those of existing keys in T, we first search the tree T. The search will be unsuccessful, then we insert the key at the point the search terminated. For instance, to insert a key 80 into the Figure 1(a), we first search the tree for 80. This search terminates unsuccessfully, and the last node examined has key 40. We insert a new node containing 80 as the right child of the node. The resulting search tree is shown in Figure 1(b).

In this problem, we consider binary search trees with N keys 1, 2,..., N. For a permutation a₁ a₂ ... a_N of {1, 2,..., N}, inserting a₁ a₂ ... a_N successively into an initially empty binary search tree will produce a binary search tree. For instance, the permutation 2 1 4 3 5 will produce the tree in Figure 1(c). Also, 2 4 3 1 5 will produce the same tree. Actually, 8 permutations among all possible permutations of 1, 2, 3, 4, 5 will produce the same tree to the tree in Figure 1(c).

We are interested in finding the number of permutations of {1, 2,..., N} such that all those permutations produce a binary search tree identical to the tree produced by a given permutation P. Given N and P, you are to write a program that calculates the number of permutations satisfying the above condition.

Input 

Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line. Each test case starts with a line containing an integer N representing the number of keys, 1N20. In the next line, a permutation of length N is given. There is a single space between the integers representing keys in the permutation.

Output 

Your program is to write to standard output. Print exactly one line for each test case as follows: Let B be the number of permutations that produce the binary search tree identical to the tree produced by the input permutation. Print B mod 9, 999, 991 for each test case. For example, if B = 20, 000, 000, the output should be 18 for that test case.

The following shows sample input and output for three test cases.

Sample Input 

3
5
2 1 4 3 5
4
2 4 1 3
12
1 2 3 4 5 6 7 8 9 10 11 12

Sample Output 

8
3
1

---

詢問有幾種排法, 跟指定輸入的產生的 BST 長得一樣,
很明顯得, 這是一個排列組合問題,
[parent]-[left]-[right]
對於一個父節點而言, left 的節點個數 x, right 的節點個數 y,
則排法 C(x+y, x), 因此對於每個節點都這麼做, 便可得到答案

#include <stdio.h>
typedef struct{
    int l, r, v, p;
    int total;
} Node;
Node bnode[21];
int bsize;
int main() {
    int t, n, i, j, x;
    scanf("%d", &t);
    long long pascal[21][21] = {};
    pascal[0][0] = 1;
    for(i = 1; i <= 20; i++) {
        pascal[i][0] = 1;
        for(j = 1; j <= i; j++)
            pascal[i][j] = pascal[i-1][j] + pascal[i-1][j-1];
    }
    while(t--) {
        scanf("%d", &n);
        scanf("%d", &bnode[0].v);
        bnode[0].l = bnode[0].r = 0;
        bnode[0].p = -1;
        bnode[0].total = 1;
        bsize = 0;
        for(i = 1; i < n; i++) {
            scanf("%d", &x);
            int idx = 0;
            while(true) {
                bnode[idx].total++;
                if(bnode[idx].v > x) {
                    if(bnode[idx].l) {
                        idx = bnode[idx].l;
                    } else {
                        bnode[idx].l = ++bsize;
                        break;
                    }
                } else {
                    if(bnode[idx].r) {
                        idx = bnode[idx].r;
                    } else {
                        bnode[idx].r = ++bsize;
                        break;
                    }
                }
            }
            bnode[bsize].v = x;
            bnode[bsize].l = bnode[bsize].r = 0;
            bnode[bsize].p = idx;
            bnode[bsize].total = 1;
        }
        long long ans = 1;
        int x, y;
        for(i = 0; i < n; i++) {
            if(bnode[i].p != -1) {
                if(bnode[bnode[i].p].r == i) {
                    if(bnode[bnode[i].p].l) {
                        x = bnode[i].total;
                        y = bnode[bnode[bnode[i].p].l].total;
                        ans *= pascal[x+y][y];
                        ans %= 9999991;
                    }
                }
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}