f.cpp

ACM训练题解 最新版 共8题 ACM训练题解 最新版 共8题

// Problem F
// http://acm.zju.edu.cn/show_problem.php?pid=2711
// Solution by semiconductor
#include	<cstdio>
#include	<cstdlib>
#include	<cstring>

using namespace std;
const char NUL = '\0';

const int MN = 61;
const int LEN = 100;

struct BigN {
	int d[LEN / 4];
	int len;
};

int N;
BigN f[MN][MN][MN];

void
Print(const BigN n, char *str = "\n")
{
	printf("%d", n.d[n.len - 1]);
	for ( int i = n.len - 2; i >= 0; i-- ) 
		printf("%04d", n.d[i]);
	printf("%s", str);
}

void
Add(BigN &a, const BigN &b)
{
	a.len >?= b.len;
	int c = 0;
	for ( int i = 0; i < a.len; i++ ) {
		a.d[i] += b.d[i] + c;
		c = 0;
		if ( a.d[i] >= 10000 ) {
			a.d[i] -= 10000;
			c = 1;
		}
	}
	if ( c ) a.d[a.len++] = 1;
}

void
Dp(void)
{
	memset(&f[N][N][N], 0, sizeof(BigN));
	f[N][N][N].d[0] = 1;
	f[N][N][N].len = 1;
	for ( int a = N; a >= 0; a-- ) 
	for ( int b = a; b >= 0; b-- ) 
	for ( int c = b; c >= 0; c-- ) {
		if ( a == N && b == N && c == N ) continue;
		BigN &res = f[a][b][c];
		memset(&res, 0, sizeof res);
		res.len = 1;
		if ( a < N ) memcpy(&res, &f[a + 1][b][c], sizeof(BigN));
		if ( b < N && a >= b + 1 ) Add(res, f[a][b + 1][c]);
		if ( c < N && b >= c + 1 ) Add(res, f[a][b][c + 1]);
	}
	Print(f[0][0][0]);
}

int
main()
{
	while ( scanf("%d", &N) != EOF ) {
		Dp();
		printf("\n");
	}
}