这题的规律是很好找的,难的就是需要用高精度进行计算。

于是我…厚颜无耻地逃避了高精度,用 Python 打了个表:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def locate(x):
a = [1, 3]
for i in range(2, x):
a.append(a[-1] + a[-2])
# print(a)
return a[x - 1]

def solve(x):
t = locate(x)
if x % 2 == 1:
return t ** 2
else:
return t ** 2 - 4

n = int(input())
print(solve(n))

C++ 交表:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
// ==============================
// author: memset0
// website: https://memset0.cn
// ==============================
#include <bits/stdc++.h>
#define ll long long
#define rep(i,l,r) for (int i = l; i <= r; i++)
#define getc(x) getchar(x)
#define putc(x) putchar(x)

template <typename T> inline void read(T &x) {
x = 0; register char ch; register bool fl = 0;
while (ch = getc(), ch < 48 || 57 < ch) fl ^= ch == '-'; x = (ch & 15);
while (ch = getc(), 47 < ch && ch < 58) x = (x << 1) + (x << 3) + (ch & 15);
if (fl) x = -x;
}
template <typename T> inline void print(T x, char c = ' ') {
static int buf[40];
if (x == 0) { putc('0'); putc(c); return; }
if (x < 0) putc('-'), x = -x;
for (buf[0] = 0; x; x /= 10) buf[++buf[0]] = x % 10 + 48;
while (buf[0]) putc((char) buf[buf[0]--]);
putc(c);
}

void init();

int n;
std::string ans[101];

int main() {

init();

read(n);
std::cout << ans[n] << std::endl;

return 0;
}

void init() {
ans[1] = "1";
ans[2] = "5";
ans[3] = "16";
ans[4] = "45";
ans[5] = "121";
ans[6] = "320";
ans[7] = "841";
ans[8] = "2205";
ans[9] = "5776";
ans[10] = "15125";
ans[11] = "39601";
ans[12] = "103680";
ans[13] = "271441";
ans[14] = "710645";
ans[15] = "1860496";
ans[16] = "4870845";
ans[17] = "12752041";
ans[18] = "33385280";
ans[19] = "87403801";
ans[20] = "228826125";
ans[21] = "599074576";
ans[22] = "1568397605";
ans[23] = "4106118241";
ans[24] = "10749957120";
ans[25] = "28143753121";
ans[26] = "73681302245";
ans[27] = "192900153616";
ans[28] = "505019158605";
ans[29] = "1322157322201";
ans[30] = "3461452808000";
ans[31] = "9062201101801";
ans[32] = "23725150497405";
ans[33] = "62113250390416";
ans[34] = "162614600673845";
ans[35] = "425730551631121";
ans[36] = "1114577054219520";
ans[37] = "2918000611027441";
ans[38] = "7639424778862805";
ans[39] = "20000273725560976";
ans[40] = "52361396397820125";
ans[41] = "137083915467899401";
ans[42] = "358890350005878080";
ans[43] = "939587134549734841";
ans[44] = "2459871053643326445";
ans[45] = "6440026026380244496";
ans[46] = "16860207025497407045";
ans[47] = "44140595050111976641";
ans[48] = "115561578124838522880";
ans[49] = "302544139324403592001";
ans[50] = "792070839848372253125";
ans[51] = "2073668380220713167376";
ans[52] = "5428934300813767249005";
ans[53] = "14213134522220588579641";
ans[54] = "37210469265847998489920";
ans[55] = "97418273275323406890121";
ans[56] = "255044350560122222180445";
ans[57] = "667714778405043259651216";
ans[58] = "1748099984655007556773205";
ans[59] = "4576585175559979410668401";
ans[60] = "11981655542024930675232000";
ans[61] = "31368381450514812615027601";
ans[62] = "82123488809519507169850805";
ans[63] = "215002084978043708894524816";
ans[64] = "562882766124611619513723645";
ans[65] = "1473646213395791149646646121";
ans[66] = "3858055874062761829426214720";
ans[67] = "10100521408792494338631998041";
ans[68] = "26443508352314721186469779405";
ans[69] = "69230003648151669220777340176";
ans[70] = "181246502592140286475862241125";
ans[71] = "474509504128269190206809383201";
ans[72] = "1242282009792667284144565908480";
ans[73] = "3252336525249732662226888342241";
ans[74] = "8514727565956530702536099118245";
ans[75] = "22291846172619859445381409012496";
ans[76] = "58360810951903047633608127919245";
ans[77] = "152790586683089283455442974745241";
ans[78] = "400010949097364802732720796316480";
ans[79] = "1047242260609005124742719414204201";
ans[80] = "2741715832729650571495437446296125";
ans[81] = "7177905237579946589743592924684176";
ans[82] = "18791999880010189197735341327756405";
ans[83] = "49198094402450621003462431058585041";
ans[84] = "128802283327341673812651951847998720";
ans[85] = "337208755579574400434493424485411121";
ans[86] = "882823983411381527490828321608234645";
ans[87] = "2311263194654570182037991540339292816";
ans[88] = "6050965600552329018623146299409643805";
ans[89] = "15841633607002416873831447357889638601";
ans[90] = "41473935220454921602871195774259272000";
ans[91] = "108580172054362347934782139964888177401";
ans[92] = "284266580942632122201475224120405260205";
ans[93] = "744219570773534018669643532396327603216";
ans[94] = "1948392131377969933807455373068577549445";
ans[95] = "5100956823360375782752722586809405045121";
ans[96] = "13354478338703157414450712387359637585920";
ans[97] = "34962478192749096460599414575269507712641";
ans[98] = "91532956239544131967347531338448885552005";
ans[99] = "239636390525883299441443179440077148943376";
ans[100] = "627376215338105766356982006981782561278125";
}