首页 > 代码库 > BZOJ 1002 轮状病毒
BZOJ 1002 轮状病毒
Description
给定n(N<=100),编程计算有多少个不同的n轮状病毒。
Input
第一行有1个正整数n。
Output
将编程计算出的不同的n轮状病毒数输出
Sample Input
3
Sample Output
16
两种做法:
1.基尔霍夫矩阵+高斯消元暴搓
2.根据基尔霍夫矩阵推出推出递推公式推出f[i]=(f[i-2]*3-f[i-1]+2)。(解释见:http://vfleaking.blog.163.com/blog/static/17480763420119685112649/)
代码如下:
#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>using namespace std;int n;struct node{ int a[1100],l; node() { memset(a,0,sizeof(a)); l = 1; } friend inline node operator *(int x,node &y) { node ret; ret.l = y.l+1; for (int i = 1;i <= y.l;++i) { ret.a[i] += y.a[i]*x; ret.a[i+1] += ret.a[i]/10; ret.a[i] %= 10; } if (ret.a[ret.l] == 0) ret.l--; return ret; } friend inline node operator -(node x,node y) { node z; z.l = max(x.l,y.l); for (int i = 1;i <= z.l;++i) { z.a[i] = x.a[i]-y.a[i]; while (z.a[i] < 0) z.a[i] += 10,x.a[i+1]--; } while (z.l > 1&&z.a[z.l] == 0)z.l--; return z; } friend inline node operator +(node &x,int y) { node ret = x; ret.a[1] += y; for (int i = 1;i <= ret.l;++i) { if (ret.a[i] >= 10) ret.a[i]-=10,ret.a[i+1]++; else break; } if (ret.a[ret.l+1]) ret.l++; return ret; } inline void print() { for (int i = l;i >= 1;--i) printf("%d",this->a[i]); }}f[110];int main(){ freopen("1002.in","r",stdin); freopen("1002.out","w",stdout); scanf("%d ",&n); f[1] = f[1]+1; f[2] = f[2] + 5; for (int i = 3;i <= n;++i) { f[i] = 3*f[i-1]; f[i] = f[i]-f[i-2]; f[i] = f[i]+2; } f[n].print(); fclose(stdin); fclose(stdout); return 0;}
BZOJ 1002 轮状病毒
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。