nbhkdz.com冰点文库

轮状病毒

时间:2016-02-02


此文章已于 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 《生成树的计数及其应用》周冬


轮状病毒肠炎临床路径(县医院2013年版)

轮状病毒肠炎临床路径 (县医院 2013 年版) 一、轮状病毒肠炎临床路径标准住院流程 (一)适用对象。 第一诊断为轮状病毒肠炎(ICD-10:A08.001) (二)诊断依据。...

口服轮状病毒活疫苗说明书

口服轮状病毒活疫苗说明书 Specificaticn for Live Rotavirus Vaccine, Oral 【药品名称】 通用名:口服轮状病毒活疫苗 英文名:live Eotavirus Vaccine, Oral 汉语...

轮状病毒的传播途径

轮状病毒的传播途径_生物学_自然科学_专业资料。轮状病毒的传播途径1 主要经粪—口或口—口传播,亦可通过水源传播或呼吸道传播,成人轮状病毒性腹泻常 呈水型暴发...

治疗轮状病毒

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

轮状病毒的的健康教育

轮状病毒腹泻是由轮状病毒引起的胃肠道感染性腹泻,轮状病毒主要于每年的11月至来年5月侵袭5岁以内的儿童,是秋冬季引起小儿死亡的主要原因之一。几乎所有儿童在5...

宝宝轮状病毒性腹泻治疗

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

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

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

轮状病毒抗原检测试剂盒

轮状病毒抗原检测试剂盒(胶体金法)说明书【产品名称】通用名称:轮状病毒抗原检测试剂盒(胶体金法) 英文名称:BIOLINE ROTAVIRUS 【包装规格】20 人份/盒 【预期...

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

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

轮状病毒症状治疗与预防

轮状病毒症状治疗与预防_临床医学_医药卫生_专业资料。轮状病毒症状治疗与预防 腹泻,俗称“拉肚子”,是儿童常见疾病,一般不会引起家长过分关注,止 泻药或抗生素一般...