2148.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2148 on 2005-10-22 at 01:55:26 */ 
#include <cstdio>
#include <cstring>

const int MAX = 1024;
const int N_MAX = 64;
const long LIMIT = 100000000;

class BigInt {
private:
	int getLength(long m) {
		int len;
		for(len = 0; m > 0; len++) {
			m /= 10;
		}
		return len;
	}
public:
	long n[N_MAX];
	BigInt() {
		memset(n, 0, sizeof(n));
	}
	void add(BigInt *a, int d = 1) {
		int i;
		for(i = 0; i < N_MAX-1; i++) {
			n[i] += a->n[i] * d;
			if(n[i] >= LIMIT) {
				n[i+1] += n[i] / LIMIT;
				n[i] %= LIMIT;
			}
		}
	}
	void set(long d) {
		n[0] = d;
	}
	void println() {
		bool havePrint = false;
		int i, j, len;
		for(i = N_MAX-1; i >= 0; i--) {
			if(n[i] != 0) {
				len = 8 - getLength(n[i]);
				if(havePrint) {
					for(j = 0; j < len; j++) {
						putchar('0');
					}
				}
				printf("%ld", n[i]);
				havePrint = true;
			} else {
				if(havePrint) {
					printf("00000000");
				}
			}
		}
		if(!havePrint) {
			putchar('0');
		}
		putchar('\n');
	}
};

class Step {
public:
	BigInt zz;
	BigInt zo;
	BigInt oz;
	BigInt oo;
};

int main()
{
	Step step[MAX];
	BigInt f[MAX];
	int i, n;
	
	f[0].set(1);
	for(i = 1; i < MAX; i++) {
		f[i].add(&f[i-1], 2);
	}
	step[1].zo.set(1);
	for(i = 2; i < MAX; i++) {
		step[i].zz.add(&step[i-1].zo);
		step[i].zo.add(&f[i-2]);
		step[i].zo.add(&step[i-1].zz);
		step[i].oz.add(&f[i-2]);
		step[i].oz.add(&step[i-1].oo);
		step[i].oo.add(&step[i-1].oz);
	}
	while(scanf("%d", &n) == 1) {
		step[n].zz.println();
	}
	
	return 0;
}