bzoj 1002 FJOI2007 轮状病毒

给定n(N<=100)，编程计算有多少个不同的n轮状病毒。

Input

第一行有1个正整数n。

Output

将编程计算出的不同的n轮状病毒数输出

Sample Input

Sample Output

代码

基尔霍夫矩阵（我也不知道是什么）推出f[i]=(f[i-1]*3-f[i-2]+2)

表示不会

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 using namespace std;
 7 struct data
 8 {
 9     int a[101],len;
10 };
11 int n;
12 data mul(data a,int k)
13 {
14     for(int i=1;i<=a.len;i++)
15         a.a[i]*=k;
16     for(int i=1;i<=a.len;i++)
17     {
18         a.a[i+1]+=a.a[i]/10;
19         a.a[i]%=10;
20     }
21     if(a.a[a.len+1]!=0) a.len++;
22     return a;
23 } 
24 data sub(data a,data b)
25 {
26     a.a[1]+=2;
27     int j=1;
28     while(a.a[j]>=10){a.a[j]%=10;a.a[j+1]++;j++;} 
29     for(int i=1;i<=a.len;i++)
30     {
31            a.a[i]-=b.a[i];
32            if(a.a[i]<0){a.a[i]+=10;a.a[i+1]--;}
33     }
34     while(a.a[a.len]==0)a.len--;
35     return a;
36 }
37 int main()
38 {
39     data f[101];
40     f[1].a[1]=1;f[2].a[1]=5;
41     f[1].len=f[2].len=1;
42     scanf("%d",&n);
43     for(int i=3;i<=n;i++)
44         f[i]=sub(mul(f[i-1],3),f[i-2]);
45     for(int i=f[n].len;i>0;i--)
46        printf("%d",f[n].a[i]);
47 }