题目描述

一列火车n节车厢,依次编号为1,2,3,…,n。每节车厢有两种运动方式,进栈与出栈,问n节车厢出栈的可能排列方式有多少种。

输入

一个数,n(n<=60000)

输出

一个数s表示n节车厢出栈的可能排列方式
 

题解:

这题要用大数,java

然后卡特兰数:有个数学模型 s[i]=c(n,2n)/(n+1)

组合数公式:这个总是记不住
这个题不能直接求,会TLE。需要先求出结果的每个质因数有多少次幂,然后用快速幂求,再把所有求幂得到的结果乘起来。
http://www.cnblogs.com/sciorz/p/9263122.html
import java.math.*;
import java.util.*;
public class Main {//筛法求素数
static final int maxn=120050;
static boolean[]isprime=new boolean[maxn];
static int[] prime=new int[maxn];
static int pz=0;
static void getPrime() {
for(int i = 2; i < maxn; ++i) isprime[i]=true;
for(int i = 2; i < maxn; ++i) {
if(isprime[i]) prime[pz++]=i;
for(int j = 0; j < pz&&(long)i*prime[j]<maxn; ++j) {
isprime[i*prime[j]]=false;
if(i%prime[j]==0) break;
}
}
}
static Scanner cin=new Scanner(System.in);
static int n=0;
public static void main(String[] args) {
n=cin.nextInt();
getPrime();
BigInteger ans=B(1);
for(int i = 0; i < pz&&prime[i]<=2*n; ++i) {
int cnt=0,p=prime[i];
int t=n*2;
while(t>0) {//(2n!)
cnt+=t/p;
t/=p;
}
t=n;
while(t>0) {//(n!*n!)
cnt-=t/p*2;
t/=p;
}
ans=ans.multiply(pow(p,cnt));
}
System.out.println(ans.divide(B(n+1)));
}
static BigInteger pow(int x,int n) {//快速积
BigInteger ans=B(1),base=B(x);
while(n>0) {
if(n%2==1) ans=ans.multiply(base);
base=base.multiply(base);
n>>=1;
}
return ans;
}
static BigInteger B(int x) {
return BigInteger.valueOf(x);
}
}

最新文章

  1. Kernel Methods (5) Kernel PCA
  2. DOM对象与JQUERY对象的相互转化
  3. CSS权威指南 - 基本视觉格式化 1
  4. C#类和成员的修饰符
  5. Codevs 1078 ==Poj 1258 Agri-Net
  6. HDU 4628 Pieces(DP + 状态压缩)
  7. Ipad亚麻布纹背景-最终效果_学习教程
  8. Android动画效果
  9. Grunt使用心得
  10. Android 使用开源xUtils来实现多线程下载(非原创)
  11. 怎样在Windows和Linux下写相同的代码
  12. c++的vector容器
  13. 《并行程序设计导论》——MPI(Microsoft MPI)(6):并行排序算法
  14. Django 下载和初识
  15. D. Time to go back(思维)
  16. [BJOI2014]大融合
  17. 转:WCF传送二进制流数据基本实现步骤详解
  18. [转发]将Delphi的对象方法设为回调函数
  19. QuickXDev插件自己主动升级后player no exist
  20. SQL查询日历

热门文章

  1. Python说文解字_Python之多任务_01
  2. Freemarker的一点延生
  3. 0CTF-2016-piapiapia-PHP反序列化长度变化尾部字符串逃逸
  4. XCOM串口助手打印不出数据
  5. GitHub的学习和使用
  6. 18 11 13 装了ssd 继续 网络通信 tcp 客户端的创建
  7. HTTP协议PUT与POST
  8. Println(Object)小贴士
  9. coures包下载和安装 可解决报错ImportError: No module named &#39;_curses&#39;
  10. 201403-1 相反数 Java