POJ3472空心方格铺砖问题（高精度计算）

题目背景：在一个尺寸为(n+1)×(n+1)的网格中，中心存在一个尺寸为(n-1)×(n-1)的空白区域。任务是使用1×2的矩形砖块来完全覆盖剩余的区域，不允许砖块重叠或超出边界。需要计算所有可能的铺设方式的数量。

理论依据：该问题可以通过数学模型解决，具体公式参考论文《Tiling with Dominoes and Fibonacci Numbers》（链接：http://www.math.unam.mx/EMIS/journals/JIS/VOL7/Tauraso/tauraso3.pdf）。论文中详细介绍了利用斐波那契数列来计算此类问题的方法。

以下是基于上述理论的C++代码实现：

#include 
#include 
#include 
#include 
#include 
using namespace std;

const int BASE = 10000;
class BigInteger {
public:
    int length;
    int digits[2500];
    BigInteger();
    BigInteger operator+(const BigInteger&);
    BigInteger operator-(const BigInteger&);
    BigInteger operator*(const BigInteger&);
    void print();
};

BigInteger::BigInteger() {
    length = 1;
    memset(digits, 0, sizeof(digits));
}

BigInteger BigInteger::operator+(const BigInteger& other) {
    BigInteger result;
    result.length = max(length, other.length);
    for (int i = 0; i         result.digits[i] += digits[i] + other.digits[i];
        if (result.digits[i] >= BASE) {
            result.digits[i + 1]++;
            result.digits[i] -= BASE;
        }
    }
    if (result.digits[result.length] > 0) result.length++;
    return result;
}

BigInteger BigInteger::operator-(const BigInteger& other) {
    BigInteger result(*this);
    for (int i = 0; i         result.digits[i] -= other.digits[i];
        if (result.digits[i] <0) {
            result.digits[i] += BASE;
            result.digits[i + 1]--;
        }
    }
    while (result.digits[result.length - 1] == 0 && result.length > 1) result.length--;
    return result;
}

BigInteger BigInteger::operator*(const BigInteger& other) {
    BigInteger result;
    result.length = length + other.length - 1;
    for (int i = 0; i         for (int j = 0; j             result.digits[i + j] += digits[i] * other.digits[j];
            if (result.digits[i + j] >= BASE) {
                result.digits[i + j + 1] += result.digits[i + j] / BASE;
                result.digits[i + j] %= BASE;
            }
        }
    }
    if (result.digits[result.length] > 0) result.length++;
    while (result.digits[result.length - 1] == 0 && result.length > 1) result.length--;
    return result;
}

void BigInteger::print() {
    printf("%d", digits[length - 1]);
    for (int i = length - 2; i >= 0; --i) printf("%04d", digits[i]);
    printf("\n");
}

BigInteger fib[10002];

int main() {
    fib[1] = BigInteger();
    fib[1].digits[0] = 1;
    for (int i = 2; i <= 10000; ++i) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }
    int n;
    while (scanf("%d", &n) != EOF) {
        BigInteger result;
        if (n % 2 == 1) {
            result = fib[n] * fib[n] * 2 - 1;
        } else {
            result = fib[n] * fib[n] * 2 + 1;
        }
        result = result * result * 4;
        result.print();
    }
    return 0;
}