这是一篇假题解
刚开始这道题我觉得是矩阵树定理，然而好像还得用高斯消元求行列式，不太会呀……然后想了半天dp式也没想出来，看了题解还是不太懂，最后lba，qmcp两人告诉了我一个玄学的方法。
首先f[1] = 1, f[2] = 3，然后像斐波那契一样递推直到第n项，如果n为奇数，就输出f[n] * f[n]，偶数就输出f[n] * f[n] - 4……然而并不会证明。最后提醒一下，别忘用高精度。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 using namespace std; 12 #define enter printf("\n") 13 #define space printf(" ") 14 #define Mem(a) memset(a, 0, sizeof(a)) 15 typedef long long ll; 16 typedef double db; 17 const int INF = 0x3f3f3f3f; 18 const int eps = 1e-8; 19 const int maxn = 105; 20 const int max_size = 1e3 + 5; 21 inline ll read() 22 { 23 ll ans = 0; 24 char ch = getchar(), last = ' '; 25 while(!isdigit(ch)) {last = ch; ch = getchar();} 26 while(isdigit(ch)) 27 { 28 ans = ans * 10 + ch - '0'; ch = getchar(); 29 } 30 if(last == '-') ans = -ans; 31 return ans; 32 } 33 inline void write(ll x) 34 { 35 if(x < 0) x = -x, putchar('-'); 36 if(x >= 10) write(x / 10); 37 putchar(x % 10 + '0'); 38 } 39 40 struct Big 41 { 42 int len, a[max_size]; 43 Big() {Mem(a); len = 0;} 44 void init(int x) 45 { 46 for(int i = x; i > 0; i /= 10) a[++len] = i % 10; 47 } 48 Big operator + (const Big& b)const 49 { 50 Big c; 51 int l = max(len, b.len); l++; 52 for(int i = 1; i <= l; ++i) 53 { 54 c.a[i] += (a[i] + b.a[i]) % 10; 55 c.a[i + 1] += (a[i] + b.a[i]) / 10; 56 } 57 while(l && !c.a[l]) l--; 58 c.len = l; 59 return c; 60 } 61 Big operator * (const Big& b)const 62 { 63 Big c; 64 for(int i = 1; i <= len; ++i) 65 for(int j = 1; j <= b.len; ++j) 66 { 67 c.a[i + j - 1] += a[i] * b.a[j]; 68 c.a[i + j] += c.a[i + j - 1] / 10; 69 c.a[i + j - 1] %= 10; 70 } 71 int l = len + b.len; 72 while(l && !c.a[l]) l--; 73 c.len = l; 74 return c; 75 } 76 Big operator - (const Big& b) 77 { 78 int l = max(len, b.len); 79 for(int i = 1; i <= l; ++i) 80 { 81 if(a[i] < b.a[i]) {a[i + 1]--; a[i] += 10;} 82 a[i] -= b.a[i]; 83 } 84 while(l && !a[l]) l--; 85 len = l; 86 return *this; 87 } 88 void out() 89 { 90 for(int i = len; i > 0; --i) write(a[i]); 91 } 92 }; 93 94 int n; 95 Big f[maxn], _4, ans; 96 97 int main() 98 { 99 n = read();100 f[2].init(3); f[1].init(1); _4.init(4);101 for(int i = 3; i <= n; ++i) f[i] = f[i - 1] + f[i - 2];102 ans = (n & 1) ? f[n] * f[n] : f[n] * f[n] - _4;103 ans.out(); enter;104 return 0;105 }