减舟's Blog

#include <cstdio>
#include <cstring>
#define MAXN 1010
using namespace std;
 
struct BigInteger {
    int a[MAXN];
    const static int L = 1000;
     
    BigInteger() {
        memset(a, 0, sizeof(a)); 
    }
};
 
BigInteger f[1010][2];
int n;
     
    BigInteger Init(int N) {
        BigInteger ans;
        for (int i = 1; i <= ans.L; i++) {
            ans.a[i] = N % 10;
            N /= 10;
            if (N == 0) break;
        }
        return ans;
    }
     
    BigInteger Plus(BigInteger A, BigInteger B) {
        BigInteger ans;
        int k = 0;
        for (int i = 1; i <= ans.L; i++) {
            ans.a[i] = A.a[i] + B.a[i] + k;
            k = ans.a[i] / 10, ans.a[i] %= 10;
        }
        return ans;
    }
     
    BigInteger Minus(BigInteger A, BigInteger B) {
        BigInteger ans;
        for (int i = 1; i <= ans.L; i++) ans.a[i] = A.a[i];
        for (int i = 1; i <= ans.L; i++) {
            ans.a[i] -= B.a[i];
            if (ans.a[i] < 0) { ans.a[i] += 10, ans.a[i + 1]--; }
        }
        return ans;
    }
     
    BigInteger Times(BigInteger A, int B) {
        BigInteger ans;
        for (int i = 1; i <= ans.L; i++) {
            ans.a[i] += A.a[i] * B;
            if (ans.a[i] > 9) {
                ans.a[i + 1] += ans.a[i] / 10;
                ans.a[i] %= 10;
            }
        }
        return ans;
    }
     
    void Print(BigInteger A) {
        int flag = 0;
        for (int i = A.L; i >= 1; i--) {
            if (flag) printf("%d", A.a[i]);
            else if (A.a[i] > 0) {
                printf("%d", A.a[i]);
                flag = 1;
            }
        }
        if (flag == 0) printf("0");
        printf("\n");
    }
     
    void Prepare() {
        f[0][1] = Init(1);
        f[1][1] = Init(1), f[1][0] = Init(1);
    }
     
int main() {
    scanf("%d", &n);
    Prepare();
    for (int i = 2; i < n; i++) {
        f[i][0] = Plus(f[i - 1][0], f[i - 1][1]);
        f[i][1] = Plus(f[i][0], f[i - 1][1]);
    }
    BigInteger ans;
    for (int i = 1; i <= n; i++) ans = Plus(ans, Times(Times(f[n - i][1], i), i));
    Print(ans);
    return 0;
}