火车进出栈 java
2024-10-08 08:39:26
题目描述
一列火车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);
}
}
最新文章
- Kernel Methods (5) Kernel PCA
- DOM对象与JQUERY对象的相互转化
- CSS权威指南 - 基本视觉格式化 1
- C#类和成员的修饰符
- Codevs 1078 ==Poj 1258 Agri-Net
- HDU 4628 Pieces(DP + 状态压缩)
- Ipad亚麻布纹背景-最终效果_学习教程
- Android动画效果
- Grunt使用心得
- Android 使用开源xUtils来实现多线程下载(非原创)
- 怎样在Windows和Linux下写相同的代码
- c++的vector容器
- 《并行程序设计导论》——MPI(Microsoft MPI)(6):并行排序算法
- Django 下载和初识
- D. Time to go back(思维)
- [BJOI2014]大融合
- 转:WCF传送二进制流数据基本实现步骤详解
- [转发]将Delphi的对象方法设为回调函数
- QuickXDev插件自己主动升级后player no exist
- SQL查询日历
热门文章
- Python说文解字_Python之多任务_01
- Freemarker的一点延生
- 0CTF-2016-piapiapia-PHP反序列化长度变化尾部字符串逃逸
- XCOM串口助手打印不出数据
- GitHub的学习和使用
- 18 11 13 装了ssd 继续 网络通信 tcp 客户端的创建
- HTTP协议PUT与POST
- Println(Object)小贴士
- coures包下载和安装 可解决报错ImportError: No module named &#39;_curses&#39;
- 201403-1 相反数 Java