1002: [FJOI2007]轮状病毒

Time Limit: 1 Sec  Memory Limit: 162 MB

Submit: 3045  Solved: 1687

[][][]

Description

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

Input

第一行有1个正整数n。

Output

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

Sample Input

3

Sample Output

16

【题解】

我就一个蒟蒻写什么题解呢= =

好了切入正题

请看下列解释

 

然而我并不懂基xxxxx矩阵，于是我在JSOI的时候硬推了一把

我做了大死……于是我jsoi就挂了TAT

就差不多这上面的递推式吧

某聚聚:我就推了10分钟；

我：我推了俩小时。。

哎差距啊= =

哦还有一件事，要上高精度。。

1 #include
       
         2 using namespace std; 3 struct bn { 4     int len; 5     int k[110]; 6 }f[101]; 7 // f(i)=3f(i-1)-f(i-2)+2 8 bn mul(bn a) { 9     bn ans;10     memset(ans.k,0,sizeof(ans.k));11     ans.len=a.len;12     for (int i=1;i<=a.len;++i) {13         ans.k[i]+=a.k[i]*3;14         if (ans.k[i]>=10) {15             ans.k[i+1]+=ans.k[i]/10;16             ans.k[i]%=10;17         }18     }19     if (ans.k[ans.len+1]>0) ans.len++;20     return ans;21 }22 bn addtwo(bn a) {23     bn ans;24     ans.len=a.len;25     memset(ans.k,0,sizeof(ans.k));26     for (int i=1;i<=ans.len;++i)27         ans.k[i]=a.k[i];28     ans.k[1]+=2;29     int ka=1;30     while(ans.k[ka]>=10) {31         ans.k[ka+1]+=ans.k[ka]/10;32         ans.k[ka++]%=10;33     }34     if (ka>ans.len) ans.len=ka;35     return ans;36 }37 bn xminus(bn a, bn b) {38     bn ans;39     ans.len=a.len;40     memset(ans.k,0,sizeof(ans.k));41     for (int i=1;i<=a.len;++i) {42         ans.k[i]+=a.k[i]-b.k[i];43         if (ans.k[i] < 0) {44             ans.k[i]+=10;45             ans.k[i+1]--;46         }47     }    48     while(ans.k[ans.len]==0) ans.len--;49     return ans;50 }51 int main() {52     int n; scanf("%d",&n);53     //for (int i=1;i<=n;++i) memset(f[i].k,0,sizeof(f[i].k));54     f[1].k[1]=1;f[2].k[1]=5;f[1].len=1;f[2].len=1;55     //bn ans=xminus(mul(f[2]),f[1]);56     //for (int i=ans.len;i>=1;--i) printf("%d",ans.k[i]);57     for (int i=3;i<=n;++i) f[i]=addtwo(xminus(mul(f[i-1]),f[i-2]));58     //f[n]=mul(f[2]);59     for (int i=f[n].len;i>=1;--i) printf("%d",f[n].k[i]);60     return 0;61 }