P2609 题解

· · 题解

题意：有一数列 \{a_i\}，通项公式为：

a_i=\begin{cases}0,i=0\\1,i=1\\a_\frac{i}{2},i \bmod 2=0\\a_\frac{i+1}{2}+a_\frac{i-1}{2},i \bmod 2 = 1\end{cases}

现有一数 n，求 a_n。

看见 n\in[1,10^{100}]，C 艹党一口老血，不如 Python，直接代入进去算就行了。

t = int(input())

while t > 0 :
    a = 1
    b = 0
    n = int(input())
    while n > 0 :
        if (n % 2 == 0) : a += b
        else : b += a
        n //= 2
    t -= 1
    print(b)

此段代码的意思就相当于：

#include <bits/stdc++.h>

using namespace std;

int n, t;

int main() {
    cin >> t;
    while (t--) {
        cin >> n;
        int a = 1, b = 0;
        while (n) {
            if (n % 2 == 0) a += b;
            else b += a;
            n /= 2;
        }
        cout << b << '\n';
    }
   return 0;
}

当然，这坨 C++ 代码是过不了这题的，会爆，要想用 C++ 过这题就老老实实打高精罢。

警钟：用递归会超时。