首页 > 代码库 > ZOJ 2711 Regular Words (三维Catalan数)
ZOJ 2711 Regular Words (三维Catalan数)
题目链接:ZOJ 2711 Regular Words (三维Catalan数)
题意:给出一串3*n长度的字符,其中是含有A,B,C,满足以下条件的字符串有多少种。
1.字符串中A,B,C的个数相同。
2.该字符串的前缀中 A,B,C的个数成非递减。
做法一:一个三维的Catalan数。
做法二:三维的DP。
AC代码:
import java.math.*; import java.util.*; public class Main{ public static void main(String[] args) { Scanner input = new Scanner(System.in); BigInteger a=null; int n; BigInteger f[]=new BigInteger[190]; f[1]=BigInteger.ONE; int i; for(i=2;i<=182;i++) { f[i]=f[i-1].multiply(BigInteger.valueOf(i)); } while(input.hasNext()) { n=input.nextInt(); if(n==0) { System.out.println(0); continue; } a=BigInteger.valueOf(2); a=a.multiply(f[n*3]); a=a.divide(f[n]); a=a.divide(f[n+1]); a=a.divide(f[n+2]); System.out.println(a); System.out.println(); } } }
ZOJ 2711 Regular Words (三维Catalan数)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。