nbhkdz.com冰点文库

轮状病毒


此文章已于 14:28:28 2016/1/30 重新发布到米花町 21 号

轮状病毒
题目描述 Description

输入描述 Input Description 第一行有 1 个正整数 n。

输出描述 Output Description

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

输出。

样例输入 Sample Input 3

样例输出 Sample Output 16

数据范围及提示 Data Size & Hint 0<n<=100

这题相当有难度,真正在考场上遇到这种题只能试试看找规律的办法了。

首先需要补充行列式的有关知识。 对于二阶和三阶行列式,其绝对值的求解较为简单。 如右图所示,将各实线上的三个数相乘后再相加,再减去各虚线上数字之积的和即为三阶 行列式的绝对值。

求解四阶行列式的绝对值,首先需要将四阶行列式将为三阶,再进行计算。

更高阶行列式以此类推。

接下来是关于行列式性质的补充。

1.行列式与其转置行列式相等。 2. 行列式的某一行(列)中所有的元素都乘以同一数 k ,等于用数 k 乘此行列式。
a11 D? a 21 ? a n1 a12 a 22 ? an 2 ? ? ? ?j) ( a1 j ? a1 (a2 j ? a? 2j) ? ( a nj ? a ? nj )
a11 ? a 21 ?j ? a1 ? a? 2j

? ? ?
? a1n ? a2n ? ? a nn 。

a1n a2 n ? a nn,则

3. 若 a11 a 21 D? ? a n1

? a1 j ? a2 j ? ? ? a nj

? a1n ? a2n ? ? a nn

? ? ? a n1 ? a ? nj

4. 交换行列式的两行(列),行列式变号。
推论:如果行列式有两行(列)完全相同,则此行列式为零。

5. 行列式中如果有两行(列)元素对应成比例,则此行列式为零。 6. 把行列式的某一列(行)的各元素乘以同一数然后加到另一列(行)对应的元素上去,行
列式值不变。

7. 上三角形行列式的值为对角线上个元素的乘积

题目可以简化为求解 n 轮状图的生成树个数,这里需要使用 Kirchhoff 矩阵求生成树个数 的方法。

对于无向图 G,我们定义它的关联矩阵 B 是一个 n*m 的矩阵,并且满足:如果 ek=(vi,

vj),那么 Bik 和 Bjk 一个为 1,另一个为-1,而第 k 列的其他元素均为 0。

定义 BT 为 B 的转置矩阵,根据矩阵乘法的定义,我们可以得到:

BB

T

ij

? ? Bik B
k ?1

m

T

kj

? ? Bik B jk
k ?1

m

对于矩阵 BBT,当 i=j 时, BBTij=vi 的度数;而当 i≠j 时,如果存在边(vi,vj),那么

BBTij=-1,否则 BBTij=0。
人们通常将 BBT 称为图的 Kirchhoff 矩阵。

Matrix-Tree 定理: 对于一个无向图 G,它的生成树个数等于其 Kirchhoff 矩阵任何一个 n-1 阶主子式的行列 式的绝对值。

所谓 n-1 阶主子式,就是对于任意一个 r,将 C 的第 r 行和第 r 列同时删去后的新矩阵, 用 Cr 表示。

如图

? 2 ?1 ?1 0 0 ? ? ? ? 1 3 ? 1 ? 1 0 ? ? ? ? 1 ? 1 3 0 ? 1? ? ? ? 0 ? 1 0 2 ? 1? ? 0 0 ?1 ?1 2 ? ? Kirchhoff 矩阵 C 为 ?

令 r=2,根据行列式的定义求出|detC2 |=11,而这 11 棵生成树如下图所示。

于是我们得到了求解生成树个数的一般方法。将图转化为 Kirchhoff 矩阵,再求解出其 n1 阶矩阵的绝对值。

我们假设所求 n 轮状图的 Kirchhoff 矩阵为

删除其最特殊的行列,得到

将最特殊的第一行与最后一行交换到一起

行列式被交换了 n-2 次,其值可能会变为原来的相反数,但不重要。 接下来为了方便计算,我们需要想办法消去最下角的三个数字。

现将第一行乘以-1 加到倒数第二行上,得到倒数第二行为 0 -3 1 0 … … 0 -1 3 再将第二行乘上-3,加到倒数第二行上,得到 0 0 -8 3 … … 0 -1 3 设第 i 次处理前第一个非零数为 fi,第二个为 gi,我们可以得到 0 0 0 … figi… 0 -1 3

= 3?1 + ?1 = ??1
每一次处理将第 i 行乘 fi 后加到倒数第二行 但是因为 i≤4,最终停在 0 0 0 … fn-4gn-4 -1 3 最后的处理结果为 0 0 0 … 0fn-2-1gn-2+3 最后一行的处理方式同倒数第二行类似,处理的结果为 0 0 0 … 0 hn-2in-2-1

设我们最终的得到下图所示行列式

消去最后一行的 H 后得到最后一行为 0 0 0 … 0 -(GH/F)+I 于是我们将行列式转化为了上三角形行列式 所求 Ans=|FI-GH|

= ?2 ?3 ? ?3 ?2 + 3?2 ? ?3 + ?2 ? 1 Ansn = ?2 ?3 ?2 + ?1 + ?2 ? 1 ?3

对行列式

?2 ?2 ?3 ?3

进行变形

?2 ?2 ?2 ?2 ?2 ?1 =? = ? ?2 = ?1 ?3 ?3 3?2 ? ?3 3?2 ? ?3 ?1 ?1 ?2 ?2
1 1 2 2

也就是说,这个行列式的值与 n 无关,始终等于

= ?1 + ?2 ? 2 = 3?2 ? ?3 + 3?3 ? ?4 ? 2 = 3 ?2 + ?3 ? 2 ? ?3 + ?4 ? 2 + 2 = 3?1 ? ?2 + 2
另外程序还需要使用高精度。

#include<stdio.h> #include<iostream> #include<stdlib.h> #include<string.h>

#include<math.h> using namespace std; int n; struct New { int s[1001]; }f[101],x,y; New multiply(New xx,int yy) { int i,t=0; //memset(x.s,0,sizeof(x.s)); x=xx; for(i=1;x.s[i]!=-1;i++) {x.s[i]=x.s[i]*yy+t; t=x.s[i]/10000; x.s[i]%=10000; } while(t) {if(x.s[i]==-1) x.s[i]=0; x.s[i]=t; t=x.s[i]/10000;

x.s[i]%=10000; i++; } return x; } New imadd(New xx,New yy) { int i,t=0; //memset(x.s,0,sizeof(x.s)); //memset(y.s,0,sizeof(x.s)); x=xx; y=yy; x.s[1]+=2; for(i=1;y.s[i]!=-1;i++) {x.s[i]=x.s[i]-y.s[i]-t; if(x.s[i]<0) {x.s[i]+=10000; t=1; } else t=0; }

while(t) {if(x.s[i]==-1) x.s[i]=0; x.s[i]-=t; if(x.s[i]<0) {x.s[i]+=10000; t=1; } else t=0; i++; } return x; } void work() { memset(f[1].s,-1,sizeof(f[1].s)); memset(f[2].s,-1,sizeof(f[2].s)); f[1].s[1]=1; f[2].s[1]=5; int i; for(i=3;i<=n;i++)

{memset(f[i].s,-1,sizeof(f[i].s)); f[i]=imadd(multiply(f[i-1],3),f[i-2]); } return; } void out() { int i,l; for(i=1;f[n].s[i]!=-1;i++); l=--i; while(i) {if(f[n].s[i]<1000&&i!=l) printf("0"); if(f[n].s[i]<100&&i!=l) printf("0"); if(f[n].s[i]<10&&i!=l) printf("0"); printf("%d",f[n].s[i]); i--; } return; }

int main() { scanf("%d",&n); work(); out(); return 0; }

扩展阅读: www.february30th.net 参考资料: http://www.kodenii.com/161.html http://wenku.baidu.com/link?url=DXIan9MRWxZdzRCNhmEz95LouUrwGbnqJqvq DP7dZwHK3GruqPDzx9bKLlpdl1cLM9_UbV1hcrel7rX5qzLiUDocXst71r3mxXoLrIzX nye 《生成树的计数及其应用》周冬


小儿轮状病毒性腹泻的防治

小儿轮状病毒性腹泻的防治_临床医学_医药卫生_专业资料。小儿轮状病毒性腹泻的防治要点小儿轮状病毒性腹泻的防治目前尚无治疗轮状病毒性腹泻的特效药物,一般都是对症...

轮状病毒

轮状病毒_临床医学_医药卫生_专业资料。A 群轮状病毒轮状病毒(RV)属于呼肠病毒科、轮状病毒属。1975 年由国际病毒分类委员会 (ICTV)正式命名。根据病毒的基因结...

治疗轮状病毒

治疗轮状病毒_预防医学_医药卫生_专业资料。轮状病毒腹泻的防治轮状病毒是引起婴幼儿腹泻病的重要病原。儿童可经历数次轮状病毒感染。 在 5 岁以下的儿童几乎人人...

轮状病毒防治基本知识问答

轮状病毒防治基本知识问答_医药卫生_专业资料。轮状病毒防治基本知识问答 1.什么是轮状病毒? 什么是轮状病毒? 轮状病毒于 1973 年最早由 Bishop 用电镜从澳大利亚...

宝宝轮状病毒性腹泻治疗

宝宝轮状病毒性腹泻治疗_育儿理论经验_幼儿教育_教育专区。宝宝轮状病毒性腹泻治疗 宝宝轮状病毒性腹泻治疗小儿轮状病毒性肠炎是常见的疾病,可是小儿轮状病毒性肠炎...

新生儿轮状病毒感染爆发流行的病例分析

龙源期刊网 http://www.qikan.com.cn 新生儿轮状病毒感染爆发流行的病例分析 作者:刘璇 殷峰 来源:《中国保健营养· 下旬刊》2014 年第 01 期 【摘要】目的...

新生儿轮状病毒感染的综合表现与治疗

新生儿轮状病毒感染的综合表现与治疗 【关键词】婴幼儿; 轮状病毒; 感染 轮状病毒(Human rotavirus,HRV)感染是小儿常见病、多发病,发病高峰 期在每年秋季和初冬,...

轮状病毒感染致腹泻患儿的护理措施

轮状病毒感染致腹泻患儿的护理措施_临床医学_医药卫生_专业资料。轮状病毒感染致腹泻患儿的护理措施 【摘要】目的探讨有效的护理措施在治疗轮状病毒感染致腹泻患 儿...

儿童轮状病毒感染医院感染预防

儿童轮状病毒感染医院感染预防 轮状病毒(Rotavirus)感染广泛存在,几乎 5 岁以下儿童发生过至少一次轮状病毒 感染,可反复感染;是院内感染中胃肠道部位感染的重要病...

轮状病毒肠炎伴良性惊厥的临床特征

龙源期刊网 http://www.qikan.com.cn 轮状病毒肠炎伴良性惊厥的临床特征 作者:沈建强 来源:《医学信息》2014 年第 01 期 摘要:目的 分析轮状病毒肠炎伴婴幼儿...