【题解】TYVJ 1374【火车进出栈问题(水水版)】

背景

这题我可是写的及其难受,没有注意到卡特兰数居然增长这么快,在$n==100$时都已经爆几百次$int128$了,于是用了$Java$去水,因为这里要用高精乘法,然而$C++$写高精着实鬼畜。

分析

这里就等价于求解第$n$项卡特兰数

代码

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

class Main{
    static Scanner in = new Scanner(new BufferedInputStream(System.in));

    static BigInteger[] cat = new BigInteger[666];

    static void Cat() {
        for(int i = 2;i < 101;i++) {
            cat[i] = new BigInteger("0");
            for(int j = 0;j < i;j++) {
                cat[i] = cat[i].add(cat[j].multiply(cat[i - 1 - j]));
            }
        }
    }

    public static void main(String[] args) {
        cat[0] = new BigInteger("1");
        cat[1] = new BigInteger("1");
        Cat();
        int n = in.nextInt();
        System.out.println(cat[n].toString());
    }
}

发布者:Cinema

成功的道路并不狭窄,因为大部分人都在颓废。

留下评论

电子邮件地址不会被公开。 必填项已用*标注