LightOj 1170 - Counting Perfect BST (折半枚举 + 卡特兰树)
2024-09-05 22:04:19
题目链接:
http://www.lightoj.com/volume_showproblem.php?problem=1170
题目描述:
给出一些满足完美性质的一列数(x > 1 and y > 1 such that m = xy.) 然后给出一个区间,问在这个区间中的完美数组成的搜索二叉树的个数是多少?
解题思路:
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 ;
}
最新文章
- 【JS】键盘鼠标事件
- Xutils请求服务器json数据与下载文件
- 07 SQL优化技术
- Java运算符及顺序、选择结构
- sql server 查询数据库所有的表名+字段
- 动态创建DataTable总结
- 20160727noip模拟赛zld
- Linux chmod命令修改文件与文件夹权限命令代码
- must implement the inherited abstract method DialogInterface.OnClickListener.onClick(DialogInterface, int)问题
- MVC返回http状态码
- 通过修改 Apache 的配置文件 htaccess 文件实现自定义404页面
- jQuery扩展与noConflict的用法-小示例
- Windows Server 2003 安装Sql Server 2005 问题处理
- 配置Windows Server 2012服务器远程连接支持多人同时登陆
- centos7制作本地yum源
- NotePad++ 添加HEX-Editor插件
- POJ 1966 Cable TV Network (算竞进阶习题)
- PHP和PHP-FPM 配置文件优化
- [ci]jenkins构建容器项目java-helloworld-非docker plugin模式
- JavaScript 生成n位随机数
热门文章
- .Net之路(十四)com组件、OLEDB导入EXCEL
- Aspose 直接插入SQL Server DataTalbe
- Jmeter代理服务器录制请求
- eureka-注册中心使用密码验证
- bzoj4105: [Thu Summer Camp 2015]平方运算
- Jackson 对象与json数据互转工具类JacksonUtil
- SPOJ:Dandiya Night and Violence(Bitset优化)
- bzoj1025 [SCOI2009]游戏——因数DP
- Visual Studio 中使用的正则表达式 说明
- 后台接口平台 基于Laravel 开发 快速开发数据接口