首页 > 代码库 > 洛谷 P2144 BZOJ 1003 [FJOI2007]轮状病毒
洛谷 P2144 BZOJ 1003 [FJOI2007]轮状病毒
题目描述
轮状病毒有很多变种。许多轮状病毒都是由一个轮状基产生。一个n轮状基由圆环上n个不同的基原子和圆心的一个核原子构成。2个原子之间的边表示这2个原子之间的信息通道，如图1。
n轮状病毒的产生规律是在n轮状基中删除若干边，使各原子之间有唯一一条信息通道。例如，共有16个不同的3轮状病毒，入图2所示。
给定n(N<=100)，编程计算有多少个不同的n轮状病毒。
输入输出格式
输入格式：
第一行有1个正整数n。
输出格式：
将编程计算出的不同的n轮状病毒数输出
输入输出样例
3
16
吐槽
今天(应该是昨天了)我的ubuntu感染wncry(想哭)2.0(惨痛经历)，重装了快一整个前半夜的系统，我感到极端的不爽，于是想把这道WC2017时就想a掉但一直搁置的题切了，发泄心中的郁闷。
解题思路
%%%伏特跳蚤国王VFK大佬的博客http://vfleaking.blog.163.com/blog/static/17480763420119685112649/
答案是求一个行列式的值，经过一大长串的公式推导化简(留坑)，得到一个递推式——f[1]=1，f[2]=5，f[n+2]=f[n+1]*3-f[n]+2，n>=1（或者f[n]=f[n-1]*3-f[n-2]+2，n>=3），于是开始敲吧。
源代码
一开始我写了个__in128版本的
#include<bits/stdc++.h>using namespace std;int n;__int128 a,b,c;void print(__int128 x){ if (x==0) return; if (x) print(x/10); putchar(x%10+‘0‘);}int main(){ a=1,b=5; cin>>n; if(n==1) { printf("1\n"); return 0; } if(n==2) { printf("5\n"); return 0; } n-=2; while(n--) { c=b*3-a+2; a=b; b=c; } print(c); printf("\n"); return 0;}
得了90分(评测记录)。第二个n=99的点wa了，n=99时__int128都爆了，但由于不想写高精，换成了unsigned __int128，照wa不误(评测记录)
而且BZOJ还不支持C++11，于是只得写高精了
#include<bits/stdc++.h>using namespace std;int n;int a[50],b[50],c[50];void print(int * c){ int i=49; while(c[i]==0) i--; while(i>=0) printf("%d",c[i--]);}int main(){ a[0]=1,b[0]=5; scanf("%d",&n); if(n==1) { printf("1\n"); return 0; } if(n==2) { printf("5\n"); return 0; } for(int k=3;k<=n;k++) { int len=49; while(b[len]==0) len--; for(int i=0;i<=len;i++) { c[i]=b[i]*3-a[i]; } c[0]+=2; for(int i=0;i<50;i++) { if(c[i]>9) { c[i+1]+=c[i]/10; c[i]%=10; } if(c[i]<0) { while(c[i]<0) c[i]+=10,c[i+1]--; } } for(int i=0;i<50;i++) { a[i]=b[i],b[i]=c[i]; } } print(c); printf("\n"); return 0;}
想想也有几个月没写过高精了，这么基础的姿势居然都忘的差不多了，我硬是调了快1个小时……在刷裸题学习新算法的时候还是不能忘记基础啊，还要多做点综合性的题目才行啊！
洛谷 P2144 BZOJ 1003 [FJOI2007]轮状病毒