题目： http://61.187.179.132/JudgeOnline/problem.php?id=1002
a[i]=a[i-1]*3-a[i-2]
对于奇数：a[1]=1 a[2]=4
答案为 a[(n-1)/2]^2
对于偶数：a[1]=1 a[2]=3
答案为 a[n/2]^2*5
1
#include <iostream>
2#include <cstdlib>
3#include <cstring>
4#include <cstdio>
5using namespace std;
6const int MaxN=105;
7const int MaxT=100;
8const int Max=10000;
9
10struct gj
11
{
12
int a[MaxT];
13
};
14
15int n;
16gj a[MaxN],c;
17
18gj gjj(gj a,gj b) //高精减
19{
20 for (int i=1;i<=b.a[0];i++)
21
{
22 a.a[i]-=b.a[i];
23 if (a.a[i]<0)
24 {
25 a.a[i]+=Max;
26 a.a[i+1]-=1;
27
}
28 }
29 for (;a.a[a.a[0]]==0;a.a[0]--);
30 if (a.a[0]==0) a.a[0]=1;
31 return a;
32}
33
34gj gjcdj(gj a,int b) //高精乘单精
35{
36
37 for (int i=a.a[0];i>=1;i--)
38 {
39 a.a[i]*=b;
40 a.a[i+1]+=a.a[i]/Max;
41 a.a[i]%=Max;
42 }
43 if (a.a[a.a[0]+1]!=0) a.a[0]++;
44 return a;
45}
46
47gj gjcgj(gj a,gj b) //高精乘高精
48{
49 memset(c.a,0,sizeof(c.a));
50 for (int i=1;i<=a.a[0];i++)
51 {
52 for (int j=1;j<=b.a[0];j++)
53 {
54 c.a[i+j-1]+=a.a[i]*b.a[j];
55 c.a[i+j-1+1]+=c.a[i+j-1]/Max;
56 c.a[i+j-1]%=Max;
57 }
58 }
59 c.a[0]=1;
60 for (;c.a[c.a[0]+1]!=0;c.a[0]++);
61 return c;
62}
63
64void write(gj a)
65{
66 printf("%d",a.a[a.a[0]]);
67 for (int i=a.a[0]-1;i>=1;i--)
68 {
69 for (int t=Max/10;t!=0;printf("%d",a.a[i]/t),a.a[i]%=t,t/=10);
70 }
71 printf("\n");
72}
73
74int main()
75{
76 memset(a,0,sizeof(a));
77 scanf("%d",&n);
78 if (n%2==1)
79 {
80 a[1].a[1]=1;
81 a[1].a[0]=1;
82 a[2].a[1]=4;
83 a[2].a[0]=1;
84 for (int i=3;i<=n/2+1;i++)
85 {
86 memcpy(a[i].a,gjcdj(a[i-1],3).a,sizeof(a[i].a));
87 memcpy(a[i].a,gjj(a[i],a[i-2]).a,sizeof(a[i].a));
88 }
89 memcpy(a[n/2+1].a,gjcgj(a[n/2+1],a[n/2+1]).a,sizeof(a[n/2+1].a));
90 write(a[n/2+1]);
91 }
92 else
93 {
94 a[0].a[1]=0;
95 a[0].a[0]=1;
96 a[1].a[1]=1;
97 a[1].a[0]=1;
98 a[2].a[1]=3;
99 a[2].a[0]=1;
100 for (int i=3;i<=n/2;i++)
101 {
102 memcpy(a[i].a,gjcdj(a[i-1],3).a,sizeof(a[i].a));
103 memcpy(a[i].a,gjj(a[i],a[i-2]).a,sizeof(a[i].a));
104 }
105 memcpy(a[n/2].a,gjcgj(a[n/2],a[n/2]).a,sizeof(a[n/2].a));
106 memcpy(a[n/2].a,gjcdj(a[n/2],5).a,sizeof(a[n/2].a));
107 write(a[n/2]);
108 }
109 return 0;
110}
111
112
113