题目地址

先拓展一下，对于斐波那契数列也就是 $f_0 = 1, f_1 = 1, f_i = f_{i - 1} + f_{i - 2}, i \ge 2$。

那么有 $\sum_{i = 0} ^ n f_i = f_{n + 2} - 1$ 如果说是 $\sum_{i = 1} ^ n f_i = f_{n + 2} - 2$。

具体来说就是考虑用 $f_{n + 2}$ 进行展开即可。

我们回到题目，考虑题目要求出的式子 $\sum_{i = 1} ^ n f_i^k$。

我们考虑对于 $f_i$ 有通向公式 $f_i = \frac{\sqrt 5}{5} (\frac{1 + \sqrt 5}{2} - \frac{1 - \sqrt 5}{2})^ i$

为了方便我们设 $a = \frac{1 + \sqrt 5}{2}, b = \frac{1 - \sqrt 5}{2}, c = \frac{\sqrt 5}{5}$

那么我们的式子就是：

$$
\begin{aligned}
Ans &= \sum_{i = 1} ^ n f_i ^ k \\
&= \sum_{i = 1} ^ n (a - b) ^ {nk} c^k\\
&= \sum_{i = 1}^n c^k \sum_{j = 0} ^ k \binom{k}{j} a^{ij} b^ {i(k-j)} \\
&= c^k \sum_{j = 0} ^ k \binom{k}{j}\sum_{i = 1} ^ n (a^jb^{k - j}) ^ i \\
&= c^k \sum_{j = 0} ^ k \binom{k}{j} \frac{(a^jb^{k - j}) ^ {n + 1} - a^jb^{k - j}}{a^jb^{k - j}-1}\\
\end{aligned}
$$

这样其实就可以使用二次剩余做了，这题就做完了。

别忘记特判如果 $a^jb^{k - j} = 1$ 那么答案就是 $n$ 了。

拓展

但是如果说 $\sqrt 5$ 没有二次剩余呢？

我们考虑进行扩域，唯一难的地方就是除法怎么做。

我们考虑分母部分可以表示成 $x + \sqrt 5 y$ 的形式，那么我们只要上下同时乘 $x - \sqrt 5 y$ 即可。

分母就进行了有理化，之后直接就可以求整数的逆元了。

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include <bits/stdc++.h>
using namespace std;
namespace Legendgod {
    namespace Read {
//        #define Fread
        #ifdef Fread
        const int Siz = (1 << 21) + 5;
        char *iS, *iT, buf[Siz];
        #define gc() ( iS == iT ? (iT = (iS = buf) + fread(buf, 1, Siz, stdin), iS == iT ? EOF : *iS ++) : *iS ++ )
        #define getchar gc
        #endif
        template <typename T>
        void r1(T &x) {
            x = 0;
            char c(getchar());
            int f(1);
            for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
            for(; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
            x *= f;
        }
        template <typename T, typename...Args>
        void r1(T &x, Args&...arg) {
            r1(x), r1(arg...);
        }
        #undef getchar
    }

using namespace Read;
//#define int long long
const int maxn = 100000 + 5;
const int mod = 1e9 + 9;

long long n, K;
struct Node {
    int x, y;// x + y * sqrt(5)
    Node(int a = 0, int b = 0) : x(a), y(b) {}
    int operator == (const Node &a) { return x == a.x && y == a.y; }
    Node operator + (const Node &a) { return Node((x + a.x) % mod, (y + a.y) % mod); }
    Node operator - (const Node &a) { return Node((x - a.x + mod) % mod, (y - a.y + mod) % mod); }
    Node operator * (const Node &a) {
        int tmp1 = (1ll * a.x * x % mod + 1ll * a.y * y % mod * 5 % mod) % mod;
        int tmp2 = (1ll * a.x * y % mod + 1ll * a.y * x % mod) % mod;
        return Node(tmp1, tmp2);
    }
}t1[maxn], t2[maxn], pw5[maxn];

int pw1[maxn], fac[maxn], finv[maxn];

int ksm(int x,int mi) {
    int res(1);
    while(mi) {
        if(mi & 1) res = 1ll * res * x % mod;
        mi >>= 1;
        x = 1ll * x * x % mod;
    }
    return res;
}

Node ksm(Node x,int mi) {
    Node res(1, 0);
    while(mi) {
        if(mi & 1) res = res * x;
        mi >>= 1;
        x = x * x;
    }
    return res;
}

void init(int x) {
    pw1[0] = 1;
    for(int i = 1; i <= x; ++ i) pw1[i] = 1ll * pw1[i - 1] * (mod - 1) % mod;
    int inv2 = ksm(2, mod - 2);
    t1[0].x = 1, t2[0].x = 1;
    t1[1] = Node(inv2, inv2);
    t2[1] = Node(inv2, mod - inv2);
    for(int i = 2; i <= x; ++ i) t1[i] = t1[i - 1] * t1[1], t2[i] = t2[i - 1] * t2[1];
    fac[0] = 1;
    for(int i = 1; i <= x; ++ i) fac[i] = 1ll * fac[i - 1] * i % mod;
    finv[x] = ksm(fac[x], mod - 2);
    for(int i = x - 1; i >= 0; -- i) finv[i] = 1ll * finv[i + 1] * (i + 1) % mod;
    pw5[0].x = 1;
    pw5[1] = Node(0, ksm(5, mod - 2));
    for(int i = 2; i <= x; ++ i) pw5[i] = pw5[i - 1] * pw5[1];
}

int C(int a,int b) {
    if(a < b || a < 0 || b < 0) return 0;
    return 1ll * fac[a] * finv[b] % mod * finv[a - b] % mod;
}

signed main() {
    int i, j, T;
    init(maxn - 5);
    r1(T);
    while(T --) {
        r1(n, K);
//        n %= (mod - 1);
        Node ans;
        for(int j = 0; j <= K; ++ j) {
            Node tmp(1ll * pw1[K - j] * C(K, j) % mod);
            Node tmp1 = t1[j] * t2[K - j];
            if(tmp1.x == 1 && tmp1.y == 0) { ans = ans + tmp * Node(n % mod, 0); continue; }
//            printf("tmp1 : %d %d\n", tmp1.x, tmp1.y);
            Node tmp2;
            Node tmp3 = tmp1;
            tmp3.x = (tmp3.x - 1 + mod) % mod;
            tmp3.y = mod - tmp3.y;

            tmp2 = ksm(tmp1, (n + 1) % (mod - 1)) - tmp1;
            tmp2 = tmp2 * tmp3;//

            tmp3 = tmp3 * Node((tmp1.x - 1 + mod) % mod, tmp1.y);
//            printf("R: %d S : %d\n", tmp3.x, tmp3.y);
            int in = ksm(tmp3.x, mod - 2);
            ans = ans + tmp * tmp2 * Node(in, 0);
        }
        ans = ans * pw5[K];
//        printf("ans : %d %d\n", ans.x, ans.y);
        printf("%d\n", ans.x);
    }
    return 0;
}

/*

1
4 20

5
10 1
4 20
20 2
9999 99
987654321987654321 98765
*/

}


signed main() { return Legendgod::main(), 0; }