<h1 id="heading">题目</h1>
<blockquote>
<h2 id="description">Description</h2>
<blockquote>
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)&gt;= B(c) &gt;= 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.
 
</blockquote>
<h2 id="input">Input</h2>
<blockquote>
There are mutiple cases in the input file.
Each case contains n (0 &lt;= n &lt;= 60 ).
There is an empty line after each case.
</blockquote>
<h2 id="output">Output</h2>
<blockquote>
Output the number of regular words of length 3n .
There should be am empty line after each case.
</blockquote>
<h2 id="sample-input">Sample Input</h2>
<blockquote>
2
3
</blockquote>
<h2 id="sample-output">Sample Output</h2>
<blockquote>
5
42
</blockquote>
</blockquote>
<h1 id="heading-1">题解</h1>
求 <code>n</code> 个以 &quot;ABC&quot; 为顺序的字符串,能拼成的字符串个数 
对于一个已知的字符串,新的字符可以插到其任意一个字符后形成新的字符串 
<code>dp[i][j][k]</code> 表示有 <code>i</code> 个 <code>A</code> <code>j</code> 个 <code>B</code> <code>k</code> 个 <code>C</code> 的字符串个数 
<code>dp[i][j][k] = dp[i-1][j][k] + dp[i][j-1][k] + dp[i][j][k-1]</code> 
要保证字符串格式正确,必须有 <code>i &gt;= j &gt;= k</code>
数比较大,需要高精度算法来运算 
由于只有60组数据,可以打表输出
<h1 id="heading-2">代码</h1>
<pre style="background-color:#fff">/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com

かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/
#include &lt;cstdio&gt;
#include &lt;algorithm&gt;
#include &lt;cstring&gt;
#include &lt;cmath&gt;
#include &lt;string&gt;
#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;list&gt;
#include &lt;queue&gt;
#include &lt;stack&gt;
#include &lt;map&gt;
#include &lt;set&gt;
#include &lt;functional&gt;
#include &lt;bitset&gt;
using namespace std;

string dp[65] = {&#34;1&#34;,&#34;1&#34;,&#34;5&#34;,&#34;42&#34;,&#34;462&#34;,&#34;6006&#34;,&#34;87516&#34;,&#34;1385670&#34;,&#34;23371634&#34;,&#34;414315330&#34;,&#34;7646001090&#34;,&#34;145862174640&#34;,&#34;2861142656400&#34;,&#34;57468093927120&#34;,&#34;1178095925505960&#34;,&#34;24584089974896430&#34;,&#34;521086299271824330&#34;,&#34;11198784501894470250&#34;,&#34;243661974372798631650&#34;,&#34;5360563436201569896300&#34;,&#34;119115896614816702500900&#34;,&#34;2670926804331443293626900&#34;,&#34;60386171228363065768956000&#34;,&#34;1375596980582110638216817680&#34;,&#34;31554078431506568639711925552&#34;,&#34;728440733705121725605657358256&#34;,&#34;16916012593818937850175820875056&#34;,&#34;394984727560107218767652172156480&#34;,&#34;9269882950945137003216002357575872&#34;,&#34;218589820552932101591964442689934272&#34;,&#34;5177405669064206309480641678873685136&#34;,&#34;123139887106265725065261170839575261246&#34;,&#34;2940211742938376804365727956142799686970&#34;,&#34;70461309651358512358741033490151564263034&#34;,&#34;1694426732092192797198296281548882854896770&#34;,&#34;40879953049935966764838175153044218787509460&#34;,&#34;989318124094680800242093703952690318964293660&#34;,&#34;24011992526103689868224096174884123328708261100&#34;,&#34;584414956558400574946623386902564355477176447080&#34;,&#34;14261150342358043298392602404780869211095488665940&#34;,&#34;348876433985002864104580005170614922408018905657020&#34;,&#34;8555006509113973886896694412506009110609925390878620&#34;,&#34;210257823823361408953856390159370731312558948560177500&#34;,&#34;5178713915261459187808923452167773648813573133021584000&#34;,&#34;127816663734641521693312994768720558317819058630953008000&#34;,&#34;3160890723051037742300958639363743464856851891194511344000&#34;,&#34;78316111638147520232116305011469771592038383559489541704000&#34;,&#34;1943917771018304520047172570820410402016667020494472553010000&#34;,&#34;48334523581589010102952513742546024844918906756931542442556400&#34;,&#34;1203813957908516875152358489329058054078745007110871474716375280&#34;,&#34;30029983483935083858438698423851117882968874317657169412268673840&#34;,&#34;750270153399794678576435057573545926324276055884108148422050727840&#34;,&#34;18772482769028405636917719941593858764528793976890630506115671775200&#34;,&#34;470373947038907707302405010980987131831213397364392909428995307126880&#34;,&#34;11802109943885320655951253002795677125946808879324767545672973160638080&#34;,&#34;296516920131524804299707608337156053506400465189952712435084509896783040&#34;,&#34;7459203321130790040650176332416188852363369960068846727881499803410725440&#34;,&#34;187875141510304732204453155491218970539216498205240765481036372897711988800&#34;,&#34;4737637890492057297860769571861620074038072983555206964113320603342642320960&#34;,&#34;119605940186192921945993199027326146131452990076639651225155962772912609414400&#34;,&#34;3022912056752362939484322031260179006906680462576858197252183463144268821651200&#34;};

bool Do() {
 int n;
 if(scanf(&#34;%d&#34;,&amp;n) == EOF)
 return false;

 cout &lt;&lt; dp[n]&lt;&lt;endl&lt;&lt;endl;

 return true;
}

int main() {
 while(Do());
 return 0;
}
</pre>

HDU 1502.Regular Words