题目描述
小白和小蓝在一起上数学课,下课后老师留了一道作业,求下面这个数列的通项公式:
小白作为一个数学爱好者,很快就计算出了这个数列的通项公式。于是,小白告诉小蓝自己已经做出来了,但为了防止小蓝抄作业,小白并不想把公式公布出来。于是小白为了向小蓝证明自己的确做出来了此题以达到其炫耀的目的,想出了一个绝妙的方法:即让小蓝说一个正整数N,小白则说出 的值,如果当N很大时小白仍能很快的说出正确答案,这就说明小白的确得到了公式。但这个方法有一个很大的漏洞:小蓝自己不会做,没法验证小白的答案是否正确。作为小蓝的好友,你能帮帮小蓝吗?
输入格式
输入文件第一行有且只有一个正整数T,表示测试数据的组数。
第2~T+1行,每行一个非负整数N。T<=20,N<=10^100。
输出格式
输出文件共包含T行。
第i行应包含一个不含多余前缀0的数,它的值应等于An(n为输入数据中第i+1行被读入的整数)。
题目解析
这道题如果直接递归计算,复杂度是指数级的,且涉及高精度计算。我们观察一下递归树,发现每一层实际需要求解的至多只有两个值,递推计算即可。复杂度。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 |
/************************************************************** Problem: 2656 User: frank_c1 Language: C++ Result: Accepted Time:1880 ms Memory:1340 kb ****************************************************************/ #include <set> #include <map> #include <queue> #include <ctime> #include <cmath> #include <cstdio> #include <vector> #include <string> #include <cctype> #include <bitset> #include <cstring> #include <cstdlib> #include <utility> #include <iostream> #include <algorithm> #define REP(i,a,b) for(int i=(a);i<=(b);i++) #define PER(i,a,b) for(int i=(a);i>=(b);i--) #define RVC(i,S) for(int i=0;i<(S).size();i++) #define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next) using namespace std; typedef long long LL; typedef pair<int,int> pii; template<class T> inline void read(T& num) { bool start=false,neg=false; char c; num=0; while((c=getchar())!=EOF) { if(c=='-') start=neg=true; else if(c>='0' && c<='9') { start=true; num=num*10+c-'0'; } else if(start) break; } if(neg) num=-num; } /*============ Header Template ============*/ char buf[5000]; struct ext { int num[5000],top; ext(int a=0) {*this=a;} int& operator[] (int k) {return num[k];} inline void clear() {top=0;memset(num,0,sizeof(num));} ext operator = (int x) { clear(); if(!x) num[++top]=0; else for(;x;num[++top]=x%10,x/=10); return *this; } ext operator = (const char* s) { clear(); top=strlen(s+1); REP(i,1,top) num[i]=s[top-i+1]-'0'; return *this; } inline void modify() { int i=1,x=0; for(;x || i<=top;i++) { x+=num[i]; num[i]=x%10; x/=10; } top=max(top,i-1); for(;top>1 && !num[top];top--); } bool operator < (const ext& b) const { if(top!=b.top) return top<b.top; PER(i,top,1) if(num[i]!=b.num[i]) return num[i]<b.num[i]; return 0; } bool operator > (const ext& b) const {return b<*this;} inline void in() {scanf("%s",buf+1);*this=buf;} inline void print() {PER(i,top,1) printf("%d",num[i]);} }; ext operator + (ext a,ext b) { ext c; c.top=max(a.top,b.top); REP(i,1,c.top) c[i]=a[i]+b[i]; c.modify(); return c; } ext operator / (ext a,int b) { ext c; c.top=0; int x=0; PER(i,a.top,1) { x=x*10+a[i]; if(x<b) continue; c[i]=x/b;x=x%b; if(!c.top) c.top=i; } if(!c.top) c.top=1; return c; } int bi[5000]; ext a,b; int main() { int T; read(T); while(T--) { a.in(); int len=0; while(a>0) bi[++len]=a[1]&1,a=a/2; a=0;b=1; PER(i,len,1) if(bi[i]) a=a+b; else b=a+b; a.print();putchar('\n'); } return 0; } |