概要

比赛地址

2020 Multi-University Training Contest 1

题目

1005. Fibonacci Sum

题目大意

令 F_i 为斐波那契数列第 i 项，求：

\sum_{i=0}^{n} (F_{i\cdot c})^k\ mod\ 1000000009

解题思路

F_n=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n+\left(\frac{1-\sqrt{5}}{2}\right)^n\right]

令：

S=\frac{1}{\sqrt{5}},\ R_1=\frac{1+\sqrt{5}}{2},\ R_2=\frac{1-\sqrt{5}}{2}

因此：

\begin{aligned}
&\ \ \ \ \sum_{i=0}^{n} (F_{i\cdot c})^k\cr
&=\sum_{i=0}^{n}S^k\cdot \sum_{j=0}^{k}\begin{pmatrix}k\cr j\end{pmatrix}(R_1)^{icj}(R_2)^{ic(k-j)}(-1)^{k-j}\cr
&=S^k\sum_{j=0}^{k}\begin{pmatrix}k\cr j\end{pmatrix}\sum_{i=0}^{n}(R_1)^{icj}(R_2)^{ic(k-j)}\cr
\end{aligned}

注意到后半部分为等比数列求和。

\sum_{i=0}^{n}{R_1}^{icj}{R_2}^{ic(k-j)}=\frac{1-\frac{{R_1}^{c(j+k)}}{{R_2}^{cj}}}{1-\left(\frac{{R_1}^{c(j+k)}}{{R_2}^{cj}}\right)^{n+1}}

令：

x=\frac{{R_1}^{c(j+k)}}{{R_2}^{cj}},\ y=\left(\frac{{R_1}^{c(j+k)}}{{R_2}^{cj}}\right)^{n+1}

开始 j=0 时，x={R_1}^{ck},\ y={R_1}^{ck(n+1)}；
每次迭代后，

x=x\cdot \frac{{R_1}^{cj}}{{R_2}^{cj}},\ y=y\cdot \frac{{R_1}^{cj(n+1)}}{{R_2}^{cj(n+1)}}

预处理出 x，y，incx，incy 可以省去枚举 k 计算等比数列求和时的一个快速幂。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e5 + 50;
const int P = 1e9 + 9;
const int sqrt5 = 383008016;
const int S = 276601605;
const int R1 = 691504013;
const int R2 = 308495997;

ll n, c;
int k;

int ksm(int a, int b) {
    if (a == 0 && b != 0) return 0;
    int ret = 1;
    for (; b; b >>= 1, a = 1LL * a * a % P) {
        if (b & 1) {
            ret = 1LL * ret * a % P;
        }
    }
    return ret;
}

int ni[N];
inline int inv(int a) {
    if (a < N) return ni[a];
    return ksm(a, P - 2);
}

void pre() {
    ni[1] = 1;
    for (int i = 2; i < N; i++) {
        ni[i] = (ll)(P - P / i) * ni[P % i] % P;
    }
}

int C[N];
void init() {
    C[0] = 1;
    for (int i = 1; i <= k; i++) {
        C[i] = (ll)C[i - 1] * (k - i + 1) % P * ni[i] % P;
    }
}

int main()
{
    pre();
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%lld%lld%d", &n, &c, &k);
        init();
        int ans = 0;
        int n2 = (n + 1) % (P - 1);
        int y = ksm(R2, c % (P - 1) * k % (P - 1));
        int x = ksm(R2, c % (P - 1) * k % (P - 1) * n2 % (P - 1));
        int rr = 1LL * R1 * inv(R2) % P;
        int incx = ksm(rr, c % (P - 1) * n2 % (P - 1));
        int incy = ksm(rr, c % (P - 1));
        for (int i = 0; i <= k; i++) {
            int tmp;
            if (y == 1) {
                tmp = 1LL * C[i] * ((n + 1) % P) % P;
            }
            else tmp = 1LL * C[i] * (x - 1) % P * inv(y - 1) % P;
            x = 1LL * x * incx % P;
            y = 1LL * y * incy % P;
            if ((k - i) & 1) {
                (ans += P - tmp) %= P;
            }
            else {
                (ans += tmp) %= P;
            }
        }
        ans = 1LL * ans * ksm(S, k) % P;
        printf("%d\n", ans);
    }
    return 0;
}