#include #include #include #include #include typedef struct AVLTreeNode{ int size; int rank; int bias; struct AVLTreeNode *left; struct AVLTreeNode *right; unsigned char val[]; } AVLNode; typedef struct AVLTreeHead{ AVLNode *root; size_t valSize; int (*cmp)(const void *,const void *); } AVLTree; int getRank(const AVLNode *t){ return t==NULL?0:t->rank; } int getSize(const AVLNode *t){ return t==NULL?0:t->size; } int getBias(const AVLNode *t){ return t==NULL?0:t->bias; } AVLNode* newAVLNode(const void *v,const size_t size){ AVLNode *res=(AVLNode *)malloc(sizeof(AVLNode)+size); memcpy(res->val,v,size); res->size=1; res->rank=1; res->bias=0; res->left=NULL; res->right=NULL; return res; } void freeAllAVLNode(AVLNode *t){ if(t==NULL) return; freeAllAVLNode(t->left); freeAllAVLNode(t->right); free(t); } void freeAVLNode(AVLNode *t){ free(t); return; } AVLTree* newAVLTree(const size_t size,int (*cmp)(const void *,const void *)){ AVLTree *res=(AVLTree *)malloc(sizeof(AVLTree)); res->root=NULL; res->valSize=size; res->cmp=cmp; return res; } void update(AVLNode *t){ if(t==NULL) return; int lrank=getRank(t->left); int rrank=getRank(t->right); t->rank=1+(lrank>rrank?lrank:rrank); t->size=1+getSize(t->left)+getSize(t->right); t->bias=lrank-rrank; return; } AVLNode* leftRotate(AVLNode *v){ AVLNode *u=v->right; v->right=u->left; u->left=v; update(v); update(u); return u; } AVLNode* rightRotate(AVLNode *u){ AVLNode *v=u->left; u->left=v->right; v->right=u; update(u); update(v); return v; } AVLNode* balance(AVLNode *t){ if(t==NULL) return NULL; int b=getBias(t); if(b<=-2){ if(getBias(t->right)>0) t->right=rightRotate(t->right); t=leftRotate(t); } else if(b>=2){ if(getBias(t->left)<0) t->left=leftRotate(t->left); t=rightRotate(t); } return t; } AVLNode* insert_func(AVLNode *r,const void *v,AVLTree *t){ if(r==NULL) return newAVLNode(v,t->valSize); if(t->cmp(r->val,v)>=0){ r->left=insert_func(r->left,v,t); } else { r->right=insert_func(r->right,v,t); } update(r); return balance(r); } void insert(AVLTree *t,const void *v){ t->root=insert_func(t->root,v,t); return; } int search(AVLTree *t,void *res){ AVLNode *r=t->root; while(r!=NULL){ int c=t->cmp(r->val,res); if(c==0){ memcpy(res,r->val,t->valSize); return 1; } else if(c>0){ r=r->left; } else { r=r->right; } } return 0; } typedef long long int int64; #define MAX(a,b) ((a)>(b)?(a):(b)) #define MIN(a,b) ((a)<(b)?(a):(b)) #define ABS(a) ((a)>(0)?(a):-(a)) const int mod=1000000000+7; int *fact=NULL; int *iFact=NULL; void init(const int n){ fact=(int *)calloc(n+1,sizeof(int)); fact[0]=1; int i; for(i=1;i<=n;i++) fact[i]=(int64)fact[i-1]*i%mod; int t=1; int a=fact[n]; while(a>1){ t=(int64)t*(mod-mod/a)%mod; a=mod%a; } iFact=(int *)calloc(n+1,sizeof(int)); iFact[n]=t; for(i=n-1;i>=0;i--) iFact[i]=(int64)iFact[i+1]*(i+1)%mod; } int comb(int n,int k){ if(!(0<=k && k<=n)) return 0; return (int64)fact[n]*iFact[k]%mod*iFact[n-k]%mod; } typedef struct { int n; int leaf; int val; } node; int cmp(const void *a,const void *b){ const node *p=(const node *)a; const node *q=(const node *)b; if(p->n !=q->n) return p->n-q->n; if(p->leaf!=q->leaf) return p->leaf-q->leaf; return 0; } int f(const int n,const int l){ if(l==1) return 1; if(l>n) return 0; static AVLTree *map=NULL; if(map==NULL) map=newAVLTree(sizeof(node),cmp); node t={n,l,0}; if(search(map,&t)) return t.val; int res=f(n-1,l); int i,j; for(i=1;i