首页 > 其他分享 >hdu1134卡特兰数

hdu1134卡特兰数

时间:2024-05-15 23:52:39浏览次数:22  
标签:aa hdu1134 BigInteger sc new 卡特兰

简单卡特兰数题,卡特兰序列:1,1,2,5,14,42,132,429,1430·············

递推式f(n)=f(n-1)*(4n-2)/ (n+1) 

import java.math.BigInteger;
import java.util.Scanner;

public class hdu1134 {

    public static void main(String[] args) {
        // TODO 自动生成的方法存根
        BigInteger aa[] = new BigInteger[101];
        aa[1] = BigInteger.ONE;
        for (int i = 2; i < aa.length; i++) {
            BigInteger bi = new BigInteger(4*i-2+"");//这里的val是十进制数字
            BigInteger bii = new BigInteger(i+1+"");
            aa[i] = aa[i-1].multiply(bi).divide(bii);
        }
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int x = sc.nextInt();
            if (x==-1) {
                break;
            }
            System.out.println(aa[x]);
        }
        sc.close();
    }
}

 

标签:aa,hdu1134,BigInteger,sc,new,卡特兰
From: https://www.cnblogs.com/xiaohuangTX/p/18195068

相关文章

  • 【数学】组合数学 - 卡特兰数
    父级页面:【数学】组合数学卡特兰数记号为\(H_n\)第n个卡特兰数,下面的n就是指这个。\(H_0=1,H_1=1,H_2=2,H_3=5,H_4=14,H_5=42\)卡特兰数最常见的场景是合法的括号序,还有栈进出的方案。他们的特点就是“右括号”、“出栈”的次数不能超过剩余的“左括号”、“入栈”的次......
  • 卡特兰数
    卡特兰数一、计算公式\(C_1=1\),\(C_n=C_{n-1}\frac{4n-2}{n+1}=C_{2n}^{n}-C_{2n}^{n+1}=\frac{C_{2n}^n}{n+1}\)二、应用场景场景1n个元素进栈序列为:1,2,3,4,...,n,则有多少种出栈序列?将进栈表示+1,出栈表示为-1。要想是合法序列,则+1的数量要大于......
  • 卡特兰数、Prüfer 序列、BSGS
    1卡特兰数1.1概述卡特兰数的前几项是$1,1,2,5,14,42,132,429,1430,4862\cdots$。卡特兰数在组合数学中有着许多应用。下面给出一个经典例子:在网格中向右或向上走,从$(0,0)$走到$(n,n)$,并且不能越过对角线的路径条数。该问题的结果就是卡特兰数,记为$H_n$。1.2通项公......
  • 卡特兰数
    为区别于组合数,用\(Cat(n)\)代表卡特兰数的第n项是一种数列,其通项公式的一种形式为:\(Cat_n=\frac{1}{n+1}\timesC_{2n}^{n}(n=0,1,2...)\)前几项数值为\(1,1,2,5,14,42,132,429\)增长幅度为\(O(4^n)\)递归定义式1\(Cat_n=\sum_{i=0}^{n-1}Cat_i\timesCat_{n-i-1}\)理解:......
  • 卡特兰数小记
    引入\(n\)个节点的二叉树个数。长度为\(2n\)的合法括号序列数量。不加说明的给出结论:上面两个问题的答案均为卡特兰数列\(H\)的第\(n\)项,\(H_n\)。暴力DP理解第一个问题设DP状态\(f(i)\)为\(i\)个节点的二叉树个数。求\(f(i)\)时,枚举左儿子节点数量\(j......
  • 关于卡特兰数
    不那么有意思的定义卡特兰数\(\big(Catalan\big)\)用\(H\)来表示,有形式如:\(H_n=\dfrac{\binom{2n}n}{n+1}(n\geq2)\)很好,你已经知道定义了。老师说:它是栈出栈入栈的\(方案数\)\(???\)放到一个递推式就有了:\(H_n=\begin{cases}H_{n-1}+H_{n-2}&\text{if}......
  • CF-1831-E-卡特兰数+异或哈希+差分
    1831-E题目大意给定一个整数\(n\),和\(k\)个区间,区间端点范围在\([1,n]\)内。如果有一个长为\(n\)合法的括号序列,且它的这\(k\)个区间\([l,r]\)中的子括号序列也是合法的,那么称这个括号序列是“好的”。请你求出有多少个长度为\(n\)的“好的”括号序列,答案对\(998244353\)取模......
  • 卡特兰数&斯特林数
    卡特兰数引入不妨从找规律开始。下标从\(0\)开始,卡特兰数的前几项为:1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845,35357670,129644790…那么通过认真的瞪眼观察,会发现它们满足递推关系。关于卡特兰数是一个很常见的数列。它并没有一个足够......
  • 火车进栈 (卡特兰数+位压高精)
    火车进栈(卡特兰数+位压高精)[题目](130.火车进出栈问题-AcWing题库)思路:车厢进出栈视为\(01\)序列,则每种\(01\)序列对应一种出栈顺序,答案即为:\({\Large\frac{1}{n+1}C_{2n}^{n}}\)数据范围:\(1{\Large\le}n{\Large\le}60000\)(数据开到\(2n\),因为这个卡了一小时qwq......
  • 卡特兰数专题(Catalan)
    卡特兰数专题(\(Catalan\))一、什么是卡特兰数?明安图数,又称卡塔兰数,英文名\(Catalan\)\(number\),是组合数学中一个常出现于各种计数问题中的数列。以中国蒙古族数学家明安图\((1692-1763)\)和比利时的数学家欧仁·查理·卡塔兰\((1814–1894)\)的名字来命名,其前几项为(从第零项开......