BZOJ

BZOJ 1002 轮状病毒

题意


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

题解

基尔霍夫矩阵（什么鬼），f[i]=(f[i-1]*3-f[i-2]+2)；f[1]=1,f[2]=5。剩下的就是高精度了。

代码

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
#include<cstdio>
struct node
{
	int a[100],len;
}f[101];
node mul(node w,int k)
{
	int yu=0;
	for (int i=1;i<=w.len;i++)
	{
		w.a[i]=w.a[i]*k+yu;
		yu=w.a[i]/10;
		w.a[i]%=10;
	}
	w.a[++w.len]=yu;
	while (w.a[w.len]==0) w.len--;
	return w;
}
node sub(node w,node y)
{
	w.a[1]+=2;
	int j=1;
    while(w.a[j]>=10){w.a[j]%=10;w.a[j+1]++;j++;} 
	for (int i=1;i<=w.len;i++)
	{
		w.a[i]-=y.a[i];
		if (w.a[i]<0) w.a[i]+=10,w.a[i+1]--;
	}
	while (w.a[w.len]==0) w.len--;
	return w;
}
int main()
{
	int n;
	scanf("%d",&n);
	f[1].a[1]=1;f[2].a[1]=5;
	f[1].len=f[2].len=1;
	for (int i=3;i<=n;i++)
		f[i]=sub(mul(f[i-1],3),f[i-2]);
	for (int i=f[n].len;i;i--)
		printf("%d",f[n].a[i]);
	return 0;
}