2 shunfurh 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
caozhy   Ds   Rxr 2017.09.18 04:25
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
ZOJ 2711 Regular Words
假设F(a,b,c)表示在当前拥有ABC/的数量分别为abc,那么F(a,b,c)=F(a-1,b,c)+F(a,b-1,c)+F(a,b,c-1)。看上去很简单,实际上的操作有两个难点。1. F(a,b,c)相当大。采用高精度加法。2.a的取值范围相当大。只能使用char数组。 #include cstdio>#include string>int N;char f[61
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
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1502
ZOJ 2711 Regular Words
简单的三维DP,需要注意的是结果很大要用到高精度,假设有a个A,b个B,c个C,f[a][b][c]表示满足条件的排列的种数,且a>=b>=c;那么如果a>b,那么最后一位可以放A; b>c;那么最后一位可以放B;如果C>0,那么最后一位可以放C;于是有f[a][b][c]=f[a-1][b][c]+f[a][b-1][c]+f[a][b][c-1],其中f[X][Y][Z]满足X>=Y>=Z;
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
给你三个字符ABC,设字符串中ABC的个数相等,再给你每个字符的个数,问在下列条件下,能形成几种排列:前i个字符中,n(A) >= n(B) >= n(C)。即A的个数大于等于B的个数大于等于C的个数。
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
题目:求由A,B,C构成的有序传中长度为n,且每个B前面的A的个数不少于当前B,每个C前面的B的个数不少于当前C的个数。 分析:dp,求排列组合数。            考虑二维的状况:                   如果 A>=B 则在 F(A-1,B)后面放上A,在F(A,B-1)后面放上B;                   F(A,B)= F(A,B-1)+ F(A-1,
VLDB 会议论文
From Regular Expressions to Nested Words:Unifying Languages and Query Execution forRelational and XML Sequences 2010年VLDB会议论文翻译。