题目大概就是求一个n个不同的数能构造出几种形态的二叉排序树。
和另一道经典题目n个结点二叉树不同形态的数量一个递推解法，其实这两个问题的解都是是卡特兰数。
- dp[n]表示用n个数的方案数
- 转移就枚举第几个数作为根，然后分成左右两子树，左右两子树的方案数的乘积就是这个数作根的方案数
另外就是题目得先找到[1,1e10]的perfect power，总共102230个；输入的区间[a,b]，b-a>=1e6，也就是最多perfect power的个数大概就在a=1,b=1000001范围内，1110个perfect power。
#include<cstdio>
#include<cstring>
#include<set>
#include<algorithm>
using namespace std;
long long pow(long long x,int y){
long long res=;
for(int i=; i<y; ++i) res*=x;
return res;
}
long long pownum[];
int pn;
int getCnt(long long a,long long b){
return (upper_bound(pownum,pownum+pn,b)-pownum)-(lower_bound(pownum,pownum+pn,a)-pownum);
}
long long d[];
int main(){
for(long long i=; i*i<=10000000000L; ++i){
for(int j=; ; ++j){
if(pow(i,j)>10000000000L) break;
pownum[pn++]=pow(i,j);
}
}
sort(pownum,pownum+pn);
pn=unique(pownum,pownum+pn)-pownum;
d[]=d[]=;
for(int i=; i<; ++i){
for(int j=; j<=i; ++j){
d[i]+=d[j-]*d[i-j];
d[i]%=;
}
}
d[]=;
long long a,b;
int t;
scanf("%d",&t);
for(int cse=; cse<=t; ++cse){
scanf("%lld%lld",&a,&b);
printf("Case %d: %lld\n",cse,d[getCnt(a,b)]);
}
return ;
}