user

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
斐波那契字

对于任意两个数字串A和B，我们定义FA,B为序列(A,B,AB,BAB,ABBAB,…)，其中每一项都是拼接前两项而成。

进一步的，取FA,B中首次包含至少n个数字的项，记其第n个数字为DA,B(n)。

举例如下：

取A=1415926535，B=8979323846。我们希望找出DA,B(35)。

FA,B的前几项分别是：
1415926535
8979323846
14159265358979323846
897932384614159265358979323846
1415926535897932384689793238461415*9*265358979323846

因此DA,B(35)是第五项的第35个数字，也就是9。

现在我们取A是圆周率π小数点后的100位数字：

14159265358979323846264338327950288419716939937510
58209749445923078164062862089986280348253421170679

B是接下来的再100位数字：

82148086513282306647093844609550582231725359408128
48111745028410270193852110555964462294895493038196 .

求∑_{n = 0,1,…,17}   10^{n}× D_{A,B}((127+19n)×7^{n})。

我的思路:首先计算这个斐波那契数列每个数字的长度.
然后设计函数f(num,pos)代表数列第num项的第pos个数字,判断如果在前部则f(num-2,pos),如果在后部则f(num-1,pos-len[num-2]),如果落到游戏初始存储AB的数字则直接返回.

请给我c++代码,可以用string存储,不用真的计算这么大的数字.

gpt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
你的思路是**完全正确而且是标准解法**，这题本质就是一个「**斐波那契字 + 第 k 位查询**」的问题，不能真的拼字符串，只能靠**长度 + 递归/迭代回溯**。

下面我会直接给你一份**可用的、结构清晰的 C++ 实现**，完全符合你描述的 `f(num, pos)` 思路，并且**不会真的生成巨大的字符串**。

---

## 一、核心思路回顾（与你一致）

定义：

* `F[0] = A`
* `F[1] = B`
* `F[n] = F[n-2] + F[n-1]`

我们只维护：

* `len[n] = |F[n]|`（可能非常大，用 `unsigned long long`，并做上界截断）

查询函数：
1
2
3
4
char get(n, pos):
    如果 n == 0 或 n == 1，直接从 A/B 中取
    如果 pos <= len[n-2] → get(n-2, pos)
    否则 → get(n-1, pos - len[n-2])
1
2
3
4
5
6
7
8
9
10
---

## 二、实现细节说明

### 1️⃣ 长度上界截断（非常重要）

`(127 + 19n) * 7^n` 在 n=17 时已经极其巨大
但我们只关心 **pos 不超过查询最大值**

所以：
1
len[i] = min(len[i-2] + len[i-1], LIMIT);
1
2
3
4
5
6
7
8
9
10
11
其中 `LIMIT` 设为大于最大查询位置即可（比如 `1e18`）。

---

### 2️⃣ 不用递归（防止栈爆）

我们用 **while 循环向下跳转**。

---

## 三、完整 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
#include <bits/stdc++.h>
using namespace std;

using ull = unsigned long long;
const ull LIMIT = (ull)1e18;

string A, B;
vector<ull> lenF;

/* 查询 F[n] 的第 pos 位（1-indexed） */
char getDigit(int n, ull pos) {
    while (n >= 2) {
        if (pos <= lenF[n - 2]) {
            n = n - 2;
        } else {
            pos -= lenF[n - 2];
            n = n - 1;
        }
    }
    // n == 0 or 1
    return (n == 0 ? A[pos - 1] : B[pos - 1]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // A: π 小数点后前 100 位
    A =
        "14159265358979323846264338327950288419716939937510"
        "58209749445923078164062862089986280348253421170679";

    // B: 接下来的 100 位
    B =
        "82148086513282306647093844609550582231725359408128"
        "48111745028410270193852110555964462294895493038196";

    // 预处理长度
    int MAXN = 100;  // 足够大
    lenF.resize(MAXN);
    lenF[0] = A.size();
    lenF[1] = B.size();

    for (int i = 2; i < MAXN; i++) {
        lenF[i] = min(lenF[i - 2] + lenF[i - 1], LIMIT);
    }

    // 计算答案
    long long ans = 0;
    ull pow7 = 1;

    for (int n = 0; n <= 17; n++) {
        ull pos = (127 + 19ULL * n) * pow7;

        // 找到第一个 lenF[k] >= pos
        int k = 0;
        while (lenF[k] < pos) k++;

        char d = getDigit(k, pos);
        ans += (long long)(d - '0') * (long long)pow(10, n);

        pow7 *= 7;
    }

    cout << ans << "\n";
    return 0;
}
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
---

## 四、复杂度分析

* **预处理长度**：`O(MAXN)`
* **每次查询**：`O(k)`，k ≈ 80
* **总复杂度**：极小，瞬间完成
* **空间**：只存字符串 + 长度数组

---

## 五、为什么这是“最优解”

✔ 不构造任何大字符串
✔ 只走索引与长度
✔ 和你给出的思路 **完全一致**
✔ 可直接过 Project Euler / NOI / 数论竞赛级别题目

---

如果你愿意，我可以：

* 给你 **递归版本**
* 给你 **模板化版本**
* 或帮你 **把这个抽象成通用 Fibonacci Word 查询类**

只要一句话 👍

fun fact

gpt一发过了.