题目大意
给定这么一个数列: [
begin{align}
a_0 &= 0, ; a1 = 1 \
a{2n} &= an \
a{2n + 1} &= an + a{n + 1}
end{align}
] 给定 (n),求 (a_n)。多组询问。
(1 leqslant T leqslant 20)
(0 leqslant n leqslant 1 times 10^{100})
题目链接
BZOJ 2656
题解
记忆化搜索 + 高精度。
代码
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
|
#include <cstring> #include <map> #include <vector> #include <algorithm> const int MAXN = 105; struct { std::vector<char> v; BigInt(int x = 0) { *this = x; } BigInt &operator=(int x) { v.clear(); do v.push_back(x % 10); while (x /= 10); return *this; } BigInt &operator=(const BigInt &x) { v.resize(x.v.size()); for (int i = 0; i < v.size(); i++) v[i] = x.v[i]; return *this; } bool operator<(const BigInt &another) const { if (v.size() != another.v.size()) return v.size() < another.v.size(); for (int i = v.size() - 1; ~i; i--) { if (v[i] != another.v[i]) return v[i] < another.v[i]; } return false; } BigInt read() { static char s[MAXN]; scanf("%s", s); v.clear(); int n = strlen(s); for (int i = n - 1; ~i; i--) v.push_back(s[i] - '0'); return *this; } bool isOdd() const { return v[0] & 1; } void print() const { for (int i = v.size() - 1; ~i; i--) putchar(v[i] + '0'); } }; BigInt operator+(const BigInt &a, const BigInt &b) { BigInt res; res.v.clear(); bool flag = false; for (int i = 0; i < std::max(a.v.size(), b.v.size()); i++) { int temp = 0; if (i < a.v.size()) temp += a.v[i]; if (i < b.v.size()) temp += b.v[i]; if (flag) temp++, flag = false; if (temp >= 10) temp -= 10, flag = true; res.v.push_back(temp); } if (flag) res.v.push_back(1); return res; } BigInt operator/(const BigInt &a, int b) { BigInt res; res.v.resize(a.v.size()); for (int i = a.v.size() - 1, temp = 0; ~i; i--) { temp = a.v[i] + temp * 10; res.v[i] = temp / b; temp %= b; } int size = res.v.size(); while (size > 1 && res.v[size - 1] == 0) size--; res.v.resize(size); return res; } static std::map<BigInt, BigInt> f; BigInt calc(const BigInt &x) { if (f.find(x) != f.end()) return f[x]; BigInt res; if (x.isOdd()) res = calc(x / 2) + calc(x / 2 + 1); else res = calc(x / 2); return f[x] = res; } int main() { f[0] = 0; f[1] = 1; int T; scanf("%d", &T); while (T--) { BigInt x; x.read(); calc(x).print(); puts(""); } return 0; }
|
近期评论