HDU 4828 逆元+catalan数

时间:2022-12-20 23:12:28

Grids

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 953    Accepted Submission(s): 418

Problem Description
  度度熊最近很喜欢玩游戏。这一天他在纸上画了一个2行N列的长方形格子。他想把1到2N这些数依次放进去,但是为了使格子看起来优美,他想找到使每行每列都递增的方案。不过画了很久,他发现方案数实在是太多了。度度熊想知道,有多少种放数字的方法能满足上面的条件?
 
Input
  第一行为数据组数T(1<=T<=100000)。
  然后T行,每行为一个数N(1<=N<=1000000)表示长方形的大小。
 
Output
  对于每组数据,输出符合题意的方案数。由于数字可能非常大,你只需要把最后的结果对1000000007取模即可。
 
Sample Input
2
1
3
 
Sample Output
Case #1:
1
Case #2:
5
Hint

对于第二组样例,共5种方案,具体方案为:HDU 4828 逆元+catalan数

 
Source
 暴力找出前几项可知  1,2,5,14,42、、、容易看出是卡特兰数,递推公式   f(n+1)=(4*n-6)/n*f(n)  |  f(1)=f(2)=1   n>=2;
由于数很大需要取模用到了逆元,这里上界100w所以用了打表法,唯一要注意的一点就是,在处理4-6/n时,由于减法可能出现负数
我们写成 ( 4-6*inv[n]+mod )的形式但是这样还是会出现负数,因为6*inv[n]可能大于mod,这里只要多加几个mod即可解决
 #include<bits/stdc++.h>
using namespace std;
#define LL long long
const LL mod=1e9+;
LL inv[]={,};
LL cat[]={,,};
void init()
{
for(int i=;i<=;++i)
inv[i]=(mod-mod/i)*inv[mod%i]%mod;
for(int i=;i<=;++i)
cat[i]=cat[i-]*((+*mod-*inv[i-])%mod)%mod;
}
int main()
{
int t,k=,i,n;
scanf("%d",&t);
init();
for(i=;i<=t;++i){
scanf("%d",&n);
printf("Case #%d:\n%lld\n",i,cat[n+]);
}
return ;
}

HDU 4828 逆元+catalan数的更多相关文章

  1. HDU 4828 - Grids &lpar;Catalan数&rpar;

    题目链接 : http://acm.hdu.edu.cn/showproblem.php?pid=4828 Catalan数的公式为 C[n+1] = C[n] * (4 * n + 2) / (n ...

  2. hdu 4828 Grids 卡特兰数&plus;逆元

    Grids Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65535/65535 K (Java/Others) Problem D ...

  3. HDU 1023 Catalan数&plus;高精度

    链接:HDU 1023 /**************************************** * author : Grant Yuan * time : 2014/10/19 15:5 ...

  4. HDU 4828 &lpar;卡特兰数&plus;逆元&rpar;

    HDU 4828 Grids 思路:能够转化为卡特兰数,先把前n个人标为0,后n个人标为1.然后去全排列,全排列的数列,假设每一个1的前面相应的0大于等于1,那么就是满足的序列.假设把0看成入栈,1看 ...

  5. HDU 4828 &lpar;卡特兰数&plus;逆&rpar;

    HDU 4828 Grids 思路:能够转化为卡特兰数,先把前n个人标为0.后n个人标为1.然后去全排列,全排列的数列.假设每一个1的前面相应的0大于等于1,那么就是满足的序列,假设把0看成入栈,1看 ...

  6. hdu 4828 Grids&lpar;拓展欧几里得&plus;卡特兰数&rpar;

    题目链接:hdu 4828 Grids 题目大意:略. 解题思路:将上一行看成是入栈,下一行看成是出栈,那么执着的方案就是卡特兰数,用递推的方式求解. #include <cstdio> ...

  7. HNU 12933 Random Walks Catalan数 阶乘求逆元新技能

    一个Catalan数的题,打表对每个数都求一次逆元会T,于是问到了一种求阶乘逆元的打表新方法. 比如打一个1~n的阶乘的逆元的表,假如叫inv[n],可以先用费马小定理什么的求出inv[n],再用递推 ...

  8. hdu 1130 How Many Trees&quest;(Catalan数)

    How Many Trees? Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) ...

  9. HDU 1023 Train Problem II 大数打表Catalan数

    一个出栈有多少种顺序的问题.一般都知道是Catalan数了. 问题是这个Catalan数非常大,故此须要使用高精度计算. 并且打表会速度快非常多.打表公式要熟记: Catalan数公式 Cn=C(2n ...

随机推荐

  1. &lbrack;TSM&rsqb;在调度计划的时候出现 &OpenCurlyDoubleQuote;ANS1125E Unmatched Quotes&colon; &&num;39&semi;string&&num;39&semi; ”错误的替代解决办法

    环境: TSMserver:TSM 6.2.3 for Windows Server 2008 R2 TSMclient: TSM 5.5.0 for CentOS 遇到的故障: ANS1125E U ...

  2. C&num; CGI程序

    一.控制面板—>程序和功能—>打开或关闭Windows功能 把相关的功能勾上,点“确定” 二.新建一个网站,配置ISAPI和CGI限制.处理程序映射 三.CGI控制台应用程序代码: usi ...

  3. Nancy Scripts&comma;CSS文件夹配置

    public class Bootstrapper : DefaultNancyBootstrapper { protected override void ConfigureConventions( ...

  4. 【读书笔记】iOS-UIFont-动态下载系统提供的多种中文字体网址

    苹果可使用的字体列表: https://support.apple.com/zh-cn/HT202599 动态下载字体的代码demo: https://developer.apple.com/libr ...

  5. 《Unix网络编程》卷2 读书笔记 第2章- Posix IPC

    1. 概述 Posix IPC 包括:Posix消息队列.Posix信号量.Posix共享内存区 Posix IPC在访问它们的函数和描述它们的信息上有一些类似点. 本章讲述所有这些共同属性:用于标识 ...

  6. linux下进程相关操作

    一.定义和理解 狭义定义:进程是正在运行的程序的实例. 广义定义:进程是一个具有一定独立功能的程序关于某个数据集合的一次运行活动. 进程的概念主要有两点: 第一,进程是一个实体.每一个进程都有它自己的 ...

  7. poj 3026 Borg Maze &lpar;最小生成树&plus;bfs&rpar;

    有几个错误,调试了几个小时,样例过后 1Y. 题目:http://poj.org/problem?id=3026 题意:就是让求A们和S的最小生成树 先用bfs找每两点的距离,再建树.没剪枝 63MS ...

  8. 【jquery学习笔记】关于&dollar;&lpar;window&rpar;&comma;&dollar;&lpar;&quot&semi;html&comma;body&quot&semi;&rpar;&period;scroll&lpar;&rpar;的在不同浏览器的不同反应

    已经很几次碰到了这种问题, 例子: $(window).scroll(function(){ var num=$(window).scrollTop();              //之前的写法是$ ...

  9. 日志收集(ElasticSearch)串联查询 MDC

    之前写过将应用程序或服务程序产生的日志直接写入搜索引擎的博客 其中基本过程就是  app->redis->logstash->elasticsearch 整个链路过程  本来想将re ...

  10. elasticsearch 安装&comma;以及遇到的问题总结

    系统.软件环境: Centos 6.5 elasticsearch 6.1.1 elasticsearch 安装的话是很简单的,但是安装完成启动的时候报错,下面我就一一的来描述错误,并提供相应的解决方 ...