本文共 3563 字，大约阅读时间需要 11 分钟。
给定n(N<=100)，编程计算有多少个不同的n轮状病毒。
第一行有1个正整数n。
将编程计算出的不同的n轮状病毒数输出
#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define rep0(i,l,r) for(int i = (l);i < (r);i++)#define rep1(i,l,r) for(int i = (l);i <= (r);i++)#define rep_0(i,r,l) for(int i = (r);i > (l);i--)#define rep_1(i,r,l) for(int i = (r);i >= (l);i--)#define MS0(a) memset(a,0,sizeof(a))#define MS1(a) memset(a,-1,sizeof(a))#define inf 0x3f3f3f3f#define lson l, m, rt << 1#define rson m+1, r, rt << 1|1//typedef __int64 ll;template void read1(T &m){ T x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} m = x*f;}template void read2(T &a,T &b){read1(a);read1(b);}template void read3(T &a,T &b,T &c){read1(a);read1(b);read1(c);}template void out(T a){ if(a>9) out(a/10); putchar(a%10+'0');}const int maxl = 1000;const int ten[5]={ 1,10,100,1000,10000};struct Biginter{ int d[maxl]; // 最大数位只取四位，因为相乘不会爆int~~,并且每次构造对象时d[]一定要为0； Biginter(char *s){ int len = strlen(s); d[0] = (len-1)/4+1;//每一个数组里面存四位，并且d[0]记录的是最多总的位数(下标) int i,j,k; for(i = 1;i <= d[0];i++) d[i] = 0; for(i = len-1;i >= 0;i--){ j = (len-1-i)/4+1; //保存的下标; k = (len-1-i)%4;//在每一个下标保存中仍然要保存顺序; d[j] += ten[k]*(s[i]-'0'); } while(d[0] > 1 && d[d[0]] == 0) d[0]--; //可能就为0; } Biginter(){MS0(d);}//手动初始化为0 void tostring(){ //输出后换行 out(d[d[0]]); for(int i = d[0]-1;i > 0;i--){ printf("%04d",d[i]); } puts(""); }};bool operator <(const Biginter& a,const Biginter& b){ if(a.d[0] != b.d[0]) return a.d[0] < b.d[0]; for(int i = a.d[0];i >= 0;i--){ if(a.d[i] != b.d[i]) return a.d[i] < b.d[i]; } return false;// a== b}bool operator ==(const Biginter& a,const Biginter& b){ if(a.d[0] != b.d[0]) return false; for(int i = a.d[0];i >= 0;i--){ if(a.d[i] != b.d[i]) return false; } return true;}Biginter operator +(const Biginter& a,const Biginter& b){ Biginter c; c.d[0] = max(a.d[0],b.d[0]); for(int i = 1;i <= c.d[0];i++){ c.d[i] += a.d[i]+b.d[i]; if(c.d[i] >= ten[4]){ //其实每次只需要看是否要进1即可; c.d[i] -= ten[4],c.d[i+1]++; if(i == c.d[0]){ ++c.d[0]; break; } } } return c;}Biginter operator -(const Biginter& a,const Biginter& b){ Biginter c; c.d[0] = a.d[0]; for(int i = 1;i <= c.d[0];i++){ c.d[i] += a.d[i] - b.d[i]; if(c.d[i] < 0){ c.d[i] += ten[4]; c.d[i+1]--; } } while(c.d[0] > 1 && c.d[c.d[0]] == 0) c.d[0]--; return c;}Biginter operator *(const Biginter& a,const Biginter& b){ Biginter c; c.d[0] = a.d[0]+b.d[0]; for(int i = 1;i <= a.d[0];i++){ int x = 0; for(int j = 1;j <= b.d[0];j++){ x += a.d[i]*b.d[j]+c.d[i+j-1]; c.d[i+j-1] = x%ten[4];//相乘时需要记录超出多少需要mod，但相加减时超出数值就是1~~不用mod更快 x /= ten[4]; } c.d[i+b.d[0]] = x;//*** } while(c.d[0] > 1 && c.d[c.d[0]] == 0) c.d[0]--; return c;}int main(){ Biginter F[101]={ "0","1","5"},F3("3"),F2("2"); rep1(i,3,100) F[i] = F[i-1]*F3 - F[i-2] + F2; int n; while(scanf("%d",&n) == 1){ F[n].tostring(); } return 0;}
转载于:https://www.cnblogs.com/hxer/p/5195196.html
