解题思路

这道题目要求我们计算有多少种不同的插入顺序可以生成相同的二叉搜索树（BST）。关键在于理解BST的构建过程以及如何计算不同插入顺序的数量。

关键点：

1. BST的构建：每次插入一个节点时，必须遵循BST的性质（左子树 ≤ 根节点 < 右子树）。
2. 插入顺序的影响：不同的插入顺序可能生成相同的BST，但必须保证根节点在其左右子树节点之前插入。
3. 组合数学：计算不同插入顺序的数量可以分解为左右子树的插入顺序的组合问题。

具体步骤：

1. 构建BST：根据给定的序列构建BST。
2. 递归计算：对于每个节点，其插入顺序的数量是其左右子树插入顺序数量的乘积，再乘以左右子树节点插入顺序的组合数。
   • 组合数计算：使用组合公式 ( C(n, k) )，表示从 ( n ) 个位置中选择 ( k ) 个位置给左子树节点，其余给右子树节点。
   • 由于模数是9901，需要使用Lucas定理来处理大组合数的模运算。
3. 模运算：由于结果可能很大，所有计算都需要对9901取模。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;
typedef long long ll;
const ll mod = 9901;
const int maxn = 110;
int n, a[maxn];
struct node{
    node *l, *r;
    int v, Size;
    node(){l=r=NULL, v=Size=0;}
}b[110];//

node *root;
void insert(int v)
{
    //printf("%d\n", v);
    node *t = root;
    while(t->Size>0)
    {
        t->Size++;
        if(v<=t->v)
        {
            if(t->l==NULL) t->l = new node();
            t = t->l;
            //printf("l%d\n", t->v);
        }
        else
        {
            if(t->r==NULL) t->r = new node();
            t = t->r;
            //printf("r%d\n", t->v);
        }
    }
    t->v = v; t->Size = 1;
}
void del(node *t)
{
    if(t->l!=NULL) del(t->l);
    if(t->r!=NULL) del(t->r);
    //printf("%d\n", t->v);
    delete(t);
}
ll mul(ll a, ll b) {return (a%mod)*(b%mod)%mod;}
ll qpow(ll a, ll b)
{
    ll res = 1; a%=mod;
    while(b)
    {
        if(b&1) res = mul(res, a);
        a = mul(a, a);
        b>>=1;
    }
    return res;
}
ll com(ll a, ll b)//Ca^b
{
    //printf("%lld %lld\n", a, b);
    if(a<b) return 0;
    if(b==0 || a==b) return 1;
    b = min(b, a-b);
    ll ca = 1, cb = 1;
    for(int i = 0; i < b; i++)
    {
        ca = mul(ca, a-i);
        cb = mul(cb, i+1);
    }
    return  mul(ca, qpow(cb, mod-2));
}
ll lucas(ll a, ll b)
{
    if(b==0) return 1;
    return com(a%mod, b%mod)*lucas(a/mod, b/mod)%mod;
}
ll dfs(node *t)
{
    if(t==NULL) return 1;
    //printf("%d %d %d %d \n", t->l==NULL?0:t->l->v, t->r==NULL?0:t->r->v, t->v, t->Size);
    return mul(mul(dfs(t->l), dfs(t->r)), lucas(t->Size-1, t->l==NULL?0:t->l->Size));
}
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    while(scanf("%d", &n) && n)
    {
        for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
        root = new node();
        root->v = a[1]; root->Size = 1;
        for(int i = 2; i <= n; i++) insert(a[i]);
        printf("%lld\n", dfs(root));
        del(root);
    }
    return 0;
}