51 nod 1236 序列求和 V3

先拓展一下，对于斐波那契数列也就是 $f_{0} = 1, f_{1} = 1, f_{i} = f_{i - 1} + f_{i - 2}, i \geq 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} A n s & = \sum_{i = 1}^{n} f_{i}^{k} \\ = \sum_{i = 1}^{n} (a - b)^{n k} c^{k} \\ = \sum_{i = 1}^{n} c^{k} \sum_{j = 0}^{k} (\binom{k}{j}) a^{i j} b^{i (k - j)} \\ = c^{k} \sum_{j = 0}^{k} (\binom{k}{j}) \sum_{i = 1}^{n} (a^{j} b^{k - j})^{i} \\ = c^{k} \sum_{j = 0}^{k} (\binom{k}{j}) \frac{(a^{j} b^{k - j})^{n + 1} - a^{j} b^{k - j}}{a^{j} b^{k - j} - 1} \end{aligned}$

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

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

拓展

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

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

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

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

cpp

#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; }