Rockdu's Blog

3

16​​

所以这道题想了很久，没有发现什么规律。然后去学(tou)习(kan)了一(ti)下(jie)，发现有个仁兄硬是画出了n = 1~5的情况（1, 5, 16, 45, 121）………………发现n为偶数时答案形如x*x-4，n为奇数答案形如x*x。并且x[1] = 1，x[2] = 3，x[i] = x[i - 1] + x[i - 2]，类似斐波那契数列。那么我们就可以递推推出答案了。（高精度封装结构体已经放在分享中）

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
int n;
namespace BIGINT {
    #define LL long long
    struct INT1024 {
        int len;
        int s[1030];
        INT1024() {clean();}
        void clean() {memset(s, 0, sizeof(s)), len = 0;}
        void operator = (int x) {
            for(; x; x /= 10) s[len++] = x % 10;
        }
        void print() {
            for(int i = len - 1; i >= 0; --i) printf("%d", s[i]);
            putchar('\n');
        }
    };
    INT1024 c;
    INT1024 operator + (INT1024 a, INT1024 b) {
        int len = max(a.len, b.len);
        c.clean();
        c.len=len;
        for(int i = 0;i < len; ++i) c.s[i] = a.s[i] + b.s[i];
        for(int i = 0;i < len; ++i) c.s[i + 1] += c.s[i] / 10, c.s[i] %= 10;
        if(c.s[len]) ++c.len;
        return c;
    }
    INT1024 operator - (INT1024 a, INT1024 b) {
        c.clean();
        for(int i = 0; i < a.len; ++i) {
            c.s[i] += a.s[i] - b.s[i];
            if(c.s[i] < 0) c.s[i] += 10, --a.s[i + 1];
        }
        int len = a.len - 1;
        for(; !c.s[len]; --len);
        c.len = len + 1;
        return c;
    }
    INT1024 operator * (INT1024 a, INT1024 b) {
        int len = a.len + b.len - 1;
        c.clean();
        c.len = len;
        for(int i = 0;i < a.len; ++i) 
            for(int j = 0; j < b.len; ++j) 
                c.s[i + j] += a.s[i] * b.s[j];
        for(int i = 0;i < len; ++i) c.s[i + 1] += c.s[i] / 10, c.s[i] %= 10;
        if(c.s[len]) ++c.len;
        return c;
    }
}
using namespace BIGINT;
INT1024 f[105];
int main() {
    f[1] = 1, f[2] = 3;
    scanf("%d", &n);
    for(register int i = 3; i <= n; ++i)
        f[i] = f[i - 1] + f[i - 2];
    INT1024 Lint = f[n] * f[n];
    INT1024 Four;
    Four = 4;
    if(n & 1) Lint.print();
    else Lint = Lint - Four, Lint.print();
    return 0;
}