shunfurh 于 2017.09.03 22:34 提问

Regular Words

Consider words of length 3n over alphabet {A, B, C} . Denote the number of occurences of A in a word a as A(a) , analogously let the number of occurences of B be denoted as B(a), and the number of occurenced of C as C(a) .

Let us call the word w regular if the following conditions are satisfied:

A(w)=B(w)=C(w) ;
if c is a prefix of w , then A(c)>= B(c) >= C(c) .
For example, if n = 2 there are 5 regular words: AABBCC , AABCBC , ABABCC , ABACBC and ABCABC .
Regular words in some sense generalize regular brackets sequences (if we consider two-letter alphabet and put similar conditions on regular words, they represent regular brackets sequences).

Given n , find the number of regular words.

Input

There are mutiple cases in the input file.

Each case contains n (0 <= n <= 60 ).

There is an empty line after each case.

Output

Output the number of regular words of length 3n .

There should be am empty line after each case.
Sample Input

2

3

Sample Output

5

42

1个回答

caozhy      2017.09.18 04:25

ZOJ 2711 Regular Words

hdu1502 Regular Words 【dp+java】
import java.math.BigInteger; import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner in=new Scanner(System.in); int n,x,y,z; BigInteger
hdu 1502 Regular Words

ZOJ 2711 Regular Words

zoj 2711 Regular Words
/* zoj_2711 dp+高精度 很简单的dp，不过结果是很大的，必须使用高精度。 */ #include #include #include using namespace std; int dp[61][61][61][21]; void print( int n ) { int i; if( n==0 ) { cout<<0; return; }
hdu 1502 Regular Words
http://acm.hdu.edu.cn/showproblem.php?pid=1502 catalan数，可以直接套公式 这里居然有DP方程，太神了 dp[i][j][k]=dp[i-1][j][k]+dp[i][j-1][k]+dp[i][j][k-1]; i-1>=j>=k,i>=j-1>=k,i>=j>=k-1 这里要分别讨论 初始化也是个问题 方程解释一下，dp[i]
【DP】HDU-1502 Regular Words

hdu 1502 Regular Words
Regular Words http://acm.hdu.edu.cn/showproblem.php?pid=1502 题目其实就是一个排列组合的问题 有n个ABC 排列有多少种排列方式 但是得保证 排列之后都能拆成ABC的模式 必须是按顺序的 排列到最后又转化成了dp的问题 最后总结出来一个公式 dp[i][j][k] = dp[i-1][j][k]+dp[i][j-1][
zoj 2711 - Regular Words

VLDB 会议论文
From Regular Expressions to Nested Words:Unifying Languages and Query Execution forRelational and XML Sequences 2010年VLDB会议论文翻译。