user

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
斐波那契数多项式

斐波那契数{fn, n ≥ 0}由递归式fn = fn-1 + fn-2给出，初值是f0 = 0和f1 = 1。

定义多项式{Fn, n ≥ 0}为Fn(x) = ∑fixi，其中0 ≤ i ≤ n。

例如，F7(x) = x + x2 + 2x3 + 3x4 + 5x5 + 8x6 + 13x7，而F7(11) = 268357683.

取n = 10^{15}。求[∑_{0≤x≤100} Fn(x)] mod 1307674368000 (= 15!)。

我的思路:矩阵快速幂.

首先枚举x.
记录F_y(x)的值,有

F_(y)(x)=(x^2)F_(y-2)(x)+(x)F_(y-1)(x)+x

那么直接维护即可.请给我c++代码

gpt

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
你的思路是**完全正确的**，而且这个题目本质上就是：

> 对每个 (x\in[0,100])，用 **矩阵快速幂** 在 (O(\log n)) 时间内算出
> (F_n(x)=\sum_{i=0}^n f_i x^i)，
> 然后求和并取模。

下面我先把递推关系**严格整理清楚**，再给你一份**可直接用的 C++ 实现**。

---

## 一、递推关系的推导（确认你写的式子）

已知：
[
f_i = f_{i-1}+f_{i-2}
]

定义：
[
F_n(x)=\sum_{i=0}^n f_i x^i
]

我们有：
[
\begin{aligned}
F_n(x)
&= F_{n-1}(x) + f_n x^n \
&= F_{n-1}(x) + (f_{n-1}+f_{n-2})x^n \
&= F_{n-1}(x) + x\cdot f_{n-1}x^{n-1} + x^2\cdot f_{n-2}x^{n-2}
\end{aligned}
]

注意到：
[
\begin{aligned}
f_{n-1}x^{n-1} &= F_{n-1}(x)-F_{n-2}(x) \
f_{n-2}x^{n-2} &= F_{n-2}(x)-F_{n-3}(x)
\end{aligned}
]

整理后可得一个**二阶非齐次线性递推**：
[
\boxed{
F_n(x) = x F_{n-1}(x) + x^2 F_{n-2}(x) + x
}
]

与你写的是一致的 ✅

---

## 二、矩阵形式

设状态向量：
[
\mathbf{v}*n=
\begin{bmatrix}
F_n(x)\
F*{n-1}(x)\
1
\end{bmatrix}
]

则：
[
\mathbf{v}*n =
\begin{bmatrix}
x & x^2 & x \
1 & 0   & 0 \
0 & 0   & 1
\end{bmatrix}
\mathbf{v}*{n-1}
]

初值：
[
F_0(x)=0,\quad F_1(x)=x
]

所以：
[
\mathbf{v}_1=
\begin{bmatrix}
x\
0\
1
\end{bmatrix}
]

我们要算：
[
\mathbf{v}_n = M^{,n-1}\mathbf{v}_1
]

---

## 三、整体复杂度

* (x = 0\sim100)，共 **101 次**
* 每次 3×3 矩阵快速幂：(O(\log n))
* 总复杂度：
  [
  O(101\cdot 3^3\log n) \quad\text{极其轻松}
  ]

---

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

static const long long MOD = 1307674368000LL; // 15!

struct Mat {
    long long a[3][3];
};

Mat mul(const Mat &A, const Mat &B) {
    Mat C{};
    for (int i = 0; i < 3; i++) {
        for (int k = 0; k < 3; k++) {
            if (A.a[i][k] == 0) continue;
            for (int j = 0; j < 3; j++) {
                __int128 tmp = (__int128)A.a[i][k] * B.a[k][j];
                C.a[i][j] = (C.a[i][j] + tmp) % MOD;
            }
        }
    }
    return C;
}

Mat mpow(Mat base, long long exp) {
    Mat res{};
    for (int i = 0; i < 3; i++) res.a[i][i] = 1;
    while (exp > 0) {
        if (exp & 1) res = mul(res, base);
        base = mul(base, base);
        exp >>= 1;
    }
    return res;
}

long long calc_Fn(long long n, long long x) {
    if (n == 0) return 0;
    if (n == 1) return x % MOD;

    Mat M{};
    M.a[0][0] = x % MOD;
    M.a[0][1] = (x * x) % MOD;
    M.a[0][2] = x % MOD;
    M.a[1][0] = 1;
    M.a[2][2] = 1;

    Mat P = mpow(M, n - 1);

    // v1 = [F1, F0, 1]^T = [x, 0, 1]
    long long Fn =
        ( (__int128)P.a[0][0] * x
        + (__int128)P.a[0][2] * 1 ) % MOD;

    return Fn;
}

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

    const long long n = 1000000000000000LL; // 10^15
    long long ans = 0;

    for (int x = 0; x <= 100; x++) {
        ans = (ans + calc_Fn(n, x)) % MOD;
    }

    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
---

## 五、几点关键说明（非常重要）

1. **一定要用 `__int128`**
   因为中间乘法最大约：
   [
   (15!)^2 \approx 10^{24}
   ]

2. **模数不是质数**
   所以不能用任何逆元或除法，只能老老实实矩阵乘。

3. **x = 0 也能正常处理**
   矩阵自然退化，代码不需要特判。

---

如果你愿意，下一步我可以帮你：

* 把 3×3 压缩成 2×2（更优雅）
* 给出数学上的生成函数解法
* 或直接证明这个递推为什么一定成立

这道题本身是**竞赛级 + 数论味道很浓**的好题 👍

fun fact

Flu认为gpt比上gemini完全不行,但是比下deepseek还是绰绰有余的,所以作为首选欧拉计划御用AI,WA了再考虑换模型.