刷题总结——regular words（hdu1502 dp+高精度加法+压位）

题目：

Problem Description

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

Sample Output

Source

Andrew Stankevich's Contest #10

Recommend

xhd

题解：

dp方程很好想：用f[a][b][c]表示A有a个B有b个C有c个的单词的总数量,则f[a][0][0]=1,f[a][b][0]=f[a-1][b][0]+f[a][b-1][0],f[a][b][c]=f[a-1][b][c]+f[a][b-1][c]+f[a][b][c-1],只是要注意f可能过大··所以要用高精度顺便压下位····

代码：

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<ctime>

#include<cctype>

#include<cstring>

#include<string>

#include<algorithm>

using namespace std;

const int N=;

const int Bit=;

int f[N][N][N][],n;

inline void add(int f1[],int f2[])

{

  int l1,l2;

  for(l1=;!f1[l1];l1--);for(l2=;!f2[l2];l2--);

  if(l1<l2)  l1=l2;

  for(int i=;i<=l1;i++)  f1[i]+=f2[i];

  for(int i=;i<=l1;i++)  f1[i+]+=f1[i]/Bit,f1[i]%=Bit;

}

inline void W(int f1[])

{

  int l1;

  for(l1=;!f1[l1];l1--);

  cout<<f1[l1];

  for(int i=l1-;i>=;i--)

  {

    if(f1[i]>=&&f1[i]<)  putchar('');

    else if(f1[i]>=&&f1[i]<)   putchar(''),putchar('');

    else if(f1[i]>=&&f1[i]<)  putchar(''),putchar(''),putchar('');

    cout<<f1[i];

  }

  cout<<endl;cout<<endl;

}

inline void getans()

{

  for(int i=;i<=;i++)

    for(int j=;j<=i;j++)

      for(int k=;k<=j;k++)

      {

        if(j==)  f[i][j][k][]=;

        else if(k==)

        {

          add(f[i][j][],f[i][j-][]);add(f[i][j][],f[i-][j][]);

        }

        else

        {

          add(f[i][j][k],f[i-][j][k]);add(f[i][j][k],f[i][j-][k]);add(f[i][j][k],f[i][j][k-]);

        }

      }

}

int main()

{

  //freopen("a.in","r",stdin);

  getans();

  while(~scanf("%d",&n))

    W(f[n][n][n]);

  return ;

}