LightOj 1170 - Counting Perfect BST (折半枚举 + 卡特兰树)

题目链接：

　　http://www.lightoj.com/volume_showproblem.php?problem=1170

题目描述：
　　给出一些满足完美性质的一列数(x > 1 and y > 1 such that m = x.) 然后给出一个区间，问在这个区间中的完美数组成的搜索二叉树的个数是多少？
解题思路：

　　1，打标算出所有的完美数列中的数字

　　2，打表算出卡特兰数列，等着以后用

　　3，卡特兰数列递推式：F[N] = F[N-1] * ( 4 * N - 2 ) / ( N + 1 )， 求余的时候牵涉到逆元，用扩展欧几里德或者费马小定理求解逆元

准备到这里就万事大吉了！

　   卡特兰数应用

代码：

　　

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 #define LL long long

 #define maxn 110100

 #define mod 100000007

 const LL Max = 1e10;

 LL a[maxn], ans[maxn], num;

 LL Extended_Euclid (LL a, LL b, LL &x, LL &y)

 {

     //处理 a * b > 0 的情况

     if (b == )

     {

         x = ;

         y = ;

         return a;

     }

     LL r = Extended_Euclid (b, a%b, x, y), t;

     t = x;

     x = y;

     y = t - a / b * y;

     return r;

 }

 void init ()

 {

     //memset (vis, 0, sizeof(vis));

     num = ;

     for (LL i=; i<maxn; i++)

     {

         LL j = i * i;

         while (j <= Max)

         {

             a[num ++] = j;

             j *= i;

         }

     }

     sort (a, a+ num);

     num = unique (a, a+num) - a;

     ans[] = ;

     ans[] = ;

     for (LL i=; i<maxn; i++)

     {

         /// F[N] = F[N-1] * ( 4 * N - 2 ) / ( N + 1 )

         LL x, y, r;

         r = Extended_Euclid (i+, mod, x, y);

         ans[i] = ans[i-] * ( * i - ) % mod * (x % mod + mod ) % mod;

     }

 }

 int main ()

 {

     init ();

     int T, L = ;

     cin >> T;

     while (T --)

     {

         LL x, y;

         scanf ("%lld %lld", &x, &y);

         x = lower_bound (a, a+num, x) - a;

         y = upper_bound (a, a+num, y) - a;

         printf ("Case %d: %lld\n", L++, ans[y - x]);

     }

     return ;

 }