AC. 梦想

frank_c1

[BZOJ 2656] 数列

发布于2016年01月18日 | 暂无评论 | 1,312阅读 | 递推,高精度

题目描述

小白和小蓝在一起上数学课，下课后老师留了一道作业，求下面这个数列的通项公式：
2016012101

小白作为一个数学爱好者，很快就计算出了这个数列的通项公式。于是，小白告诉小蓝自己已经做出来了，但为了防止小蓝抄作业，小白并不想把公式公布出来。于是小白为了向小蓝证明自己的确做出来了此题以达到其炫耀的目的，想出了一个绝妙的方法：即让小蓝说一个正整数N，小白则说出 的值，如果当N很大时小白仍能很快的说出正确答案，这就说明小白的确得到了公式。但这个方法有一个很大的漏洞：小蓝自己不会做，没法验证小白的答案是否正确。作为小蓝的好友，你能帮帮小蓝吗？

输入格式

输入文件第一行有且只有一个正整数T，表示测试数据的组数。

第2～T+1行，每行一个非负整数N。T<=20,N<=10^100。

输出格式

输出文件共包含T行。

第i行应包含一个不含多余前缀0的数，它的值应等于An(n为输入数据中第i+1行被读入的整数)。

题目解析

这道题如果直接递归计算，复杂度是指数级的，且涉及高精度计算。我们观察一下递归树，发现每一层实际需要求解的至多只有两个值，递推计算即可。复杂度O(\log {N})。

BZOJ2656
C++
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;
}


快速访问

    分类目录：

    文章归档：

随便看看

标签

Copyright © 2016 AC. 梦想 版权所有 | Powered By WordPress | Theme By YeLook