这题与前面的“踩方格”重复了，而且是大坑题！题目漏写了取模12345的条件！
详细解析请见我之前的博文——http://www.cnblogs.com/konjak/p/5936888.html
而这坑在我打了高精+滚动之后才知道。。我先把这个代码贴上来。。
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #include<iostream>
5 using namespace std;
6
7 struct node{int s[510];int l;}
8 f[3],c;//1010
9
10 int mmax(int x,int y) {return x>y?x:y;}
11 node pplus(node a,node b)
12 {
13 c.l=mmax(a.l,b.l);
14 memset(c.s,0,sizeof(c.s));
15 for (int i=1;i<=c.l;i++)
16 {
17 c.s[i]+=a.s[i]+b.s[i];
18 c.s[i+1]+=c.s[i]/10;
19 c.s[i]%=10;
20 }
21 if (c.s[c.l+1]) c.l++;
22 return c;
23 }
24
25 int main()
26 {
27 int n;
28 scanf("%d",&n);
29 f[1].l=1,f[1].s[1]=3;
30 f[2].l=1,f[2].s[1]=7;
31 int u,v,w;
32 u=0;
33 for (int i=3;i<=n;i++)
34 {
35 v=(u+2)%3,w=(u+1)%3;//v=(u+3-1)%3,w=(u+3-2)%3;
36 f[u]=pplus(pplus(f[v],f[v]),f[w]);
37 u=(u+1)%3;
38 }//f[i]=pplus(pplus(f[i-1],f[i-1]),f[i-2]);
39 int t=(u+2)%3;//(u+3-1)%3;
40 if (n<3) t=n;
41 for (int i=f[t].l;i>=1;i--)
42 printf("%d",f[t].s[i]);
43 printf("\n");
44 return 0;
45 }
高精+滚动
AC代码是这样的——
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #include<iostream>
5 using namespace std;
6
7 int f[3];
8 int main()
9 {
10 int n;
11 scanf("%d",&n);
12 f[1]=3, f[2]=7;
13 int u,v,w;
14 u=0;
15 for (int i=3;i<=n;i++)
16 {
17 v=(u+2)%3,w=(u+1)%3;
18 f[u]=(2*f[v]+f[w])%12345;
19 u=(u+1)%3;
20 }
21 if (n<3) printf("%d\n",f[n]);
22 else printf("%d\n",f[(u+2)%3]);
23 return 0;
24 }
滚动
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #include<iostream>
5 using namespace std;
6
7 long long f[1010];
8
9 int main()
10 {
11 int n;
12 scanf("%d",&n);
13 f[1]=3, f[2]=7;
14 for (int i=3;i<=n;i++)
15 f[i]=(2*f[i-1]+f[i-2])%12345;
16 printf("%lld\n",f[n]);
17 return 0;
18 }
不滚动