题解 P2609 【[ZJOI2012]数列】

一只书虫仔 · 2020-08-12 13:24:13 · 题解

Description

给定一个序列 a_i 的通项公式

a_0=0,a_1=1,a_{2i}=a_i,a_{2i+1}=a_i+a_{i+1}

给定 n，求 a_n

Solution

又是高精

这题可以进行转化，比如 a_{2i} 和 a_{2i+1}，可以转化为两个 a_i 和一个 a_{i+1}。

• a_3=a_\frac{2}{2}+a_{\frac{2}{2}+1}=a_1+a_2=a_1+a_1=0 \times a_0+2 \times a_1=2
• a_4=a_\frac{4}{2}=a_2=a_1=0 \times a_0+1 \times a_1=1

所以我们只需要求出 l 和 r 即可，因为 a_0=0,a_1=1，所以输出 r 即可。

Code 1

#include <bits/stdc++.h>

using namespace std;

int main () {
    long long t;
    scanf("%lld", &t);
    while (t--) {
        long long n;
        scanf("%lld", &n);
        long long l = 1, r = 0;
        while (n > 0) {
            if (n % 2 == 0)
                l = l + r;
            else
                r = l + r;
            n /= 2;
        }
        printf("%lld\n", r);
    }
    return 0;
}

预计得分：50 分
Record Link

让我们重新审视 n 的数据范围，n \le 10^{100}。

所以这题需要高精。

Code 2

t = int(input())

for i in range(1, t + 1) :
    n = int(input())

    l = 1
    r = 0

    while n > 0 :
        if n % 2 == 0 :
            l = l + r
        else :
            r = l + r
        n //= 2

    print(r)

预计得分：100 分
Record Link

用 python 会被骂的，所以还是要好好写 C++ 比较好

By Shuchong
2020.8.12