Seletiva IOI 2015

binaria.cpp

// Ivan Carvalho
// Binária - Seletiva IOI - OBI 2015
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 101;
const ll MOD = 1e9 + 7;
ll dp[MAXN][MAXN];
ll binomial[MAXN][MAXN];
ll N,K,H,entrada[MAXN];
ll filho_esquerdo[MAXN],filho_direito[MAXN],valor[MAXN],sz_tree[MAXN],ptr;
ll dp_na_arvore[MAXN][MAXN];
void insere(ll atual,ll novo){
	sz_tree[atual]++;
	if(novo < valor[atual]){
		if(filho_esquerdo[atual] == -1){
			filho_esquerdo[atual] = ++ptr;
			valor[ptr] = novo;
			sz_tree[ptr] = 1;
			return;
		}
		else{
			insere(filho_esquerdo[atual],novo);
		}
	}
	else{
		if(filho_direito[atual] == -1){
			filho_direito[atual] = ++ptr;
			valor[ptr] = novo;
			sz_tree[ptr] = 1;
			return;
		}
		else{
			insere(filho_direito[atual],novo);
		}
	}
}
ll escolhe(ll p,ll q){
	if(p == 0) return 1;
	if(binomial[p][q] != -1) return binomial[p][q];
	if(q == 0 || p == q) return binomial[p][q] = 1;
	return binomial[p][q] = (escolhe(p-1,q-1) + escolhe(p-1,q)) % MOD;
}
ll solve(int ini,int fim,int altura){
	fim -= ini - 1;
	ini = 1;
	int tam = fim;
	if(altura <= 0) return 0;
	if(ini > fim) return 0;
	if(dp[tam][altura] != -1) return dp[tam][altura];
	if(ini == fim){
		return dp[tam][altura] = 1;
	}
	ll total = 0;
	for(int quebra = ini;quebra <= fim;quebra++){
		if(quebra == ini){
			total += solve(quebra+1,fim,altura-1);
		}
		else if(quebra == fim){
			total += solve(ini,quebra-1,altura-1);
		}
		else{
			total += escolhe(tam - 1,quebra-1)*(solve(ini,quebra-1,altura-1)*solve(quebra+1,fim,altura-1) % MOD);
		}
		total %= MOD;
	}
	return dp[tam][altura] = total;
}
ll combinatoria(ll pos,ll ini,ll fim,ll altura){
	if(altura <= 0) return 0;
	if(ini > fim) return 0;
	if(dp_na_arvore[pos][altura] != -1) return dp_na_arvore[pos][altura] = 1;
	if(ini == fim){
		return dp_na_arvore[pos][altura] = 1;
	}
	ll idx = valor[pos];
	if(filho_esquerdo[pos] != -1 && filho_direito[pos] != -1){
		ll sz_esq = (idx - ini) - sz_tree[filho_esquerdo[pos]];
		ll sz_dir = (fim - idx) - sz_tree[filho_direito[pos]];
		ll total = escolhe(sz_esq + sz_dir,sz_esq)*(combinatoria(filho_esquerdo[pos],ini,idx-1,altura-1)*combinatoria(filho_direito[pos],idx+1,fim,altura-1) % MOD);
		total %= MOD;
		return dp_na_arvore[pos][altura] = total;
	}
	else if(filho_esquerdo[pos] != -1){
		if(idx == fim){
			return dp_na_arvore[pos][altura] = combinatoria(filho_esquerdo[pos],ini,idx-1,altura-1);
		}
		else{
			ll sz_esq = (idx - ini) - sz_tree[filho_esquerdo[pos]];
			ll sz_dir = (fim - idx);
			ll total = escolhe(sz_esq + sz_dir,sz_esq)*(combinatoria(filho_esquerdo[pos],ini,idx-1,altura-1)*solve(idx+1,fim,altura-1) % MOD);
			total %= MOD;
			return dp_na_arvore[pos][altura] = total;
		}
	}
	else if(filho_direito[pos] != -1){
		if(idx == ini){
			return dp_na_arvore[pos][altura] = combinatoria(filho_direito[pos],idx+1,fim,altura-1);
		}
		else{
		ll sz_esq = (idx - ini);
		ll sz_dir = (fim - idx) - sz_tree[filho_direito[pos]];
		ll total = escolhe(sz_esq + sz_dir,sz_esq)*(solve(ini,idx-1,altura-1)*combinatoria(filho_direito[pos],idx+1,fim,altura-1) % MOD);
		total %= MOD;
		return dp_na_arvore[pos][altura] = total;
		}
	}
	else{
		ll total = 0;
		ll sz_esq = (idx - ini);
		ll sz_dir = (fim - idx);
		if(idx == ini){
			total += solve(idx+1,fim,altura-1);
		}
		else if(idx == fim){
			total += solve(ini,idx-1,altura-1);
		}
		else{
			total += escolhe(sz_esq + sz_dir,sz_esq)*(solve(ini,idx-1,altura-1)*solve(idx+1,fim,altura-1) % MOD);
		}
		total %= MOD;
		return dp_na_arvore[pos][altura] = total;
	}
}
int main(){
	memset(binomial,-1,sizeof(binomial));
	scanf("%lld %lld %lld",&N,&K,&H);
	memset(dp,-1,sizeof(dp));
	if(K == 0){
		ll exibir = solve(1,N,H) - solve(1,N,H-1);
		if(exibir < 0) exibir += MOD;
		printf("%lld\n",exibir);
		return 0;
	}
	memset(valor,-1,sizeof(valor));
	memset(filho_esquerdo,-1,sizeof(filho_esquerdo));
	memset(filho_direito,-1,sizeof(filho_direito));
	memset(dp_na_arvore,-1,sizeof(dp_na_arvore));
	for(ll i = 1;i<=K;i++) scanf("%lld",&entrada[i]);
	ptr++;
	valor[ptr] = entrada[1];
	sz_tree[1] = 1;
	for(ll i = 2;i<=K;i++){
		insere(1,entrada[i]);
	}
	ll exibir = combinatoria(1,1,N,H) - combinatoria(1,1,N,H-1);
	if(exibir < 0) exibir += MOD;
	printf("%lld\n",exibir);
	return 0;
}