CF 126D - Fibonacci Sums 题解

1
#include <bits/stdc++.h>
2

3
#define N 90
4
using namespace std;
5

6
typedef long long ll;
7

8
vector<int> pos;
9
ll fib[N];
10
ll dp[N][2];
11

12
void init() {
13
    fib[1] = fib[2] = 1;
14
    for (int i = 3; i < N; i++) fib[i] = fib[i - 1] + fib[i - 2];
15
}
16

17
int solve(ll x) {
18
    pos.clear();
19
    for (int i = N - 1; i >= 1; i--) {
20
        if (!x) break;
21
        if (fib[i] <= x) {
22
            x -= fib[i];
23
            pos.push_back(i - 1);
24
        }
25
    }
26
    reverse(pos.begin(), pos.end());
27
    return pos.size();
28
}
29

30
int main() {
31
    ios::sync_with_stdio(false);
32
    cin.tie(nullptr);
33
    cout.tie(nullptr);
34

35
    int t;
36
    cin >> t;
37
    init();
38
    while (t--) {
39
        memset(dp, 0, sizeof dp);
40

41
        ll x;
42
        cin >> x;
43
        int len = solve(x);
44
        dp[0][0] = 1;
45
        dp[0][1] = (pos[0] - 1) / 2;
46
        for (int i = 1; i < len; i++) {
47
            dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
48
            dp[i][1] = dp[i - 1][0] * ((pos[i] - pos[i - 1] - 1) / 2) + dp[i - 1][1] * ((pos[i] - pos[i - 1]) / 2);
49
        }
50
        cout << dp[len - 1][1] + dp[len - 1][0] << endl;
51
    }
52
    return 0;
53
}