#include<cstdio>
#include<iostream>
#define MOD 9999991
#define endl '\n'
#define int long long int
using namespace std;
int C[30][30];
void init(){
for(int i=0;i<30;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];
}
}
struct BTS{
struct Node{
int k,si;
Node*ch[2];
Node(){}
Node(int _x):k(_x){ch[0]=ch[1]=NULL;si=1;}
}*root;
int si;
void init(int n){
this->si=n;
root=NULL;
}
void ins(Node*&cur,int x){
if(cur==NULL){
cur=new Node(x);
return;
}
if(x<cur->k)ins(cur->ch[0],x);
else ins(cur->ch[1],x);
cur->si=1;
if(cur->ch[0])cur->si+=cur->ch[0]->si;
if(cur->ch[1])cur->si+=cur->ch[1]->si;
}
int count(Node*cur){
if(cur==NULL)return 1;
if(cur->ch[0]&&!cur->ch[1]){
return count(cur->ch[0])%MOD;
}
else if(cur->ch[0]&&cur->ch[1]){
int sp=cur->ch[0]->si+cur->ch[1]->si;
return count(cur->ch[0])%MOD*count(cur->ch[1])%MOD*(C[sp][cur->ch[0]->si])%MOD;
}
else if(!cur->ch[0]&&cur->ch[1]){
return count(cur->ch[1])%MOD;
}
else {
return 1;
}
}
}tree;
main(){
cin.tie(0);ios_base::sync_with_stdio(false);
init();
int T;cin>>T;
while(T--){
int N;cin>>N;
tree.init(N);
for(int i=0;i<N;i++){
int a;cin>>a;
tree.ins(tree.root,a);
}
cout<<tree.count(tree.root)<<endl;
}
return 0;
}
創作內容
UVa 1264題解
生活寫照 (2)