首页 > 代码库 > [bzoj1002][FJOI2007]轮状病毒-题解[基尔霍夫矩阵][高精度][递推]
[bzoj1002][FJOI2007]轮状病毒-题解[基尔霍夫矩阵][高精度][递推]
Description
轮状病毒有很多变种，所有轮状病毒的变种都是从一个轮状基产生的。一个N轮状基由圆环上N个不同的基原子
和圆心处一个核原子构成的，2个原子之间的边表示这2个原子之间的信息通道。如下图所示
.png)
N轮状病毒的产生规律是在一个N轮状基中删去若干条边，使得各原子之间有唯一的信息通道，例如共有16个不
同的3轮状病毒，如下图所示
.png)
现给定n(N<=100)，编程计算有多少个不同的n轮状病毒
Input
第一行有1个正整数n
Output
计算出的不同的n轮状病毒数输出
Sample Input
3
Sample Output
16
首先明确一个事情，这个题与基尔霍夫矩阵有关，但是并不能用基尔霍夫矩阵做，原因等下讲。
对于一个图，我们令它的度数矩阵为D(D[i,i]表示点i的度数，其他为0)，令它的邻接矩阵为A(A[i,j]表示i是否有一条边连向j)
其基尔霍夫矩阵为D-A。
基尔霍夫矩阵可用于一个图的生成树计数，具体做法是去掉任意一行与任意一列，剩下的即是一个行列式，它左上到右下的对角线上的值的乘积就是该图生成树的数目(我真的不知道证明。。)，利用高斯消元将其变为上三角行列式然后求解即可。
但是很容易发现当n比较大时所得到的值是很大的，必须要用高精度，但是用基尔霍夫矩阵直接使用高斯消元求解是极其复杂的，所以我们不能直接用它求解。
然后我们发现这个题得到的基尔霍夫矩阵都是类似的，然后我们可以尝试找规律。
F(n) = 3*F(n - 1) - F(n - 2) + 2
有关规律的证明可以去看vfleaking的博客,有关基尔霍夫矩阵的可以去看周冬的论文,或者某阮的博客（推荐看前者）。
上代码
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 using namespace std; 6 inline int read() 7 { 8 char ch=getchar();int kin=1,gi=0; 9 while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)kin=-1;ch=getchar();}10 while(ch>=‘0‘&&ch<=‘9‘){gi=gi*10+ch-48;ch=getchar();}11 return gi*kin;12 }13 struct big14 {15 int num[105];16 int siz;17 big operator *(int x)18 {19 big tmp=*this;20 for(int i=1;i<=tmp.siz;++i)21 {22 tmp.num[i]*=x;23 }24 for(int j=1;j<=tmp.siz;++j)if(tmp.num[j]>=10)tmp.num[j+1]+=tmp.num[j]/10,tmp.num[j]%=10;25 while(tmp.num[tmp.siz+1]!=0)tmp.siz++;26 return tmp;27 }28 big operator +(int x)29 {30 big tmp=*this;31 tmp.num[1]+=x;32 for(int j=1;j<=tmp.siz;++j)if(tmp.num[j]>=10)tmp.num[j+1]+=tmp.num[j]/10,tmp.num[j]%=10;33 while(tmp.num[tmp.siz+1]!=0)tmp.siz++;34 return tmp;35 }36 big operator -(big d)37 {38 big tmp=*this;39 for(int i=1;i<=min(d.siz,tmp.siz);++i)40 {41 if(tmp.num[i]<d.num[i])tmp.num[i+1]-=1,tmp.num[i]+=10;42 if(tmp.num[i]>=d.num[i])tmp.num[i]-=d.num[i];43 }44 siz=max(d.siz,tmp.siz);45 while(tmp.num[siz]==0)siz--;46 return tmp;47 }48 }a[105];49 int n,ans=1;50 int main()51 {52 a[1].num[1]=1,a[2].num[1]=5;a[1].siz=a[2].siz=1;53 n=read();54 for(int i=2;i<n;++i)55 {56 a[i+1]=a[i]*3-a[i-1]+2;57 }58 for(int i=a[n].siz;i>0;--i)printf("%d",a[n].num[i]);59 }
[bzoj1002][FJOI2007]轮状病毒-题解[基尔霍夫矩阵][高精度][递推]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。