10198 - Counting

#include <bits/stdc++.h>

using namespace std;

#define rep(i,n) for (int i = 0, _n = (n); i < _n; i++)
#define repr(i,n) for (int i = (n) - 1; i >= 0; i--)
#define int64 long long
#define pb push_back


struct BigInteger {
    static const int BASE = 1000000000; // 10^9

    vector<int64> digits;

    BigInteger() {
        digits.clear();
        digits.pb(0);
    }
    BigInteger(int64 number) {
        digits.clear();
        do {
            digits.pb(number % BASE);
            number /= BASE;
        } while (number);
    }

    BigInteger operator + (const BigInteger &b) const {
        BigInteger res = BigInteger();
        res.digits.resize(max(b.digits.size(), digits.size()));
        int64 remainder = 0;
        rep(i, res.digits.size()) {
            if (i < int(digits.size())) remainder += digits[i];
            if (i < int(b.digits.size())) remainder += b.digits[i];
            res.digits[i] = remainder % BASE;
            remainder /= BASE;
        }
        while (remainder) {
            res.digits.pb(remainder % BASE);
            remainder /= BASE;
        }
        return res;
    }

    BigInteger operator * (const BigInteger &b) const {
        BigInteger res = BigInteger();
        res.digits = vector<int64>(b.digits.size() + digits.size() - 1, 0);
        rep(i, digits.size()) rep(j, b.digits.size())
            res.digits[i + j] += digits[i] * (int64)b.digits[j];
        int64 remainder = 0;
        rep(i, res.digits.size()) {
            remainder += res.digits[i];
            res.digits[i] = remainder % BASE;
            remainder /= BASE;
        }
        while (remainder) {
            res.digits.pb(remainder % BASE);
            remainder /= BASE;
        }
        return res;
    }

    void print() {
        printf("%lld", digits.back());
        repr(i, (int)digits.size() - 1) printf("%09lld", digits[i]);
    }

    static BigInteger power(const BigInteger &b, int64 k) {
        if (k == 0) return BigInteger(1);
        if (k == 1) return b;
        BigInteger res = power(b, k / 2);
        res = res * res;
        if (k & 1) return res * b;
        return res;
    }
};

BigInteger dp[1001][1001];
bool cached[1001][1001];

BigInteger solve(const int &n, int idx, int sum) {
    if (sum <= 0) {
        return BigInteger(sum == 0);
    }
    BigInteger &ret = dp[idx][sum];
    if (cached[idx][sum])
        return ret;

    ret = 0;
    for (int i = 1; i <= 4; i++) {
        ret = ret + solve(n, idx + 1, sum - ((i - 1) % 3 + 1));
    }
    cached[idx][sum] = true;
    return ret;
}

int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        BigInteger ans = solve(n, 0, n);
        ans.print();
        puts("");
    }
    return 0;
}