思路与算法

令Q为斐波那契转移矩阵[[1,1],[1,0]]，Q^j左上角是F(j+1)。每个坐标贡献指数i-1，所有坐标和对应S(n)^k，其中S(n)=I+Q+...+Q^(n-1)。倍增同时返回Q^n与S(n)：偶数时幂平方，和为S+Q^(n/2)S；奇数再追加末项。最后对S快速幂k，取左上角。

正确性说明

矩阵乘法满足结合与分配，展开S^k恰对所有k元坐标各出现一次，其指数和等于Σi-k，对应题设斐波那契下标Σi-k+1。倍增公式直接把几何和分成前后两半，递归归纳正确；最终矩阵幂实现该乘积。

复杂度

每组2阶矩阵初始化O(1)，几何和递归O(logn)，快速幂O(logk)，总O(logn+logk)时间、O(logn)递归空间。所有运算模1e9+7。

易错点

n=1时S=I，任意k答案1。F下标从1开始，不能直接取矩阵右上角导致少一项。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
struct Mat {
    long long a[2][2];
    Mat(int diag = 0) {
        memset(a, 0, sizeof(a));
        a[0][0] = a[1][1] = diag;
    }
};
Mat operator*(const Mat &x, const Mat &y) {
    Mat z;
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            for (int k = 0; k < 2; k++)
                z.a[i][j] = (z.a[i][j] + x.a[i][k] * y.a[k][j]) % MOD;
    return z;
}
Mat operator+(const Mat &x, const Mat &y) {
    Mat z;
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            z.a[i][j] = (x.a[i][j] + y.a[i][j]) % MOD;
    return z;
}
pair<Mat, Mat> geom(long long n) {
    if (!n)
        return {Mat(1), Mat()};
    auto z = geom(n / 2);
    Mat p = z.first * z.first, s = z.second + z.first * z.second;
    if (n % 2) {
        s = s + p;
        Mat q;
        q.a[0][0] = q.a[0][1] = q.a[1][0] = 1;
        p = p * q;
    }
    return {p, s};
}
int main() {
    int T;
    cin >> T;
    while (T--) {
        long long n, k;
        cin >> n >> k;
        Mat a = geom(n).second, r(1);
        while (k) {
            if (k & 1)
                r = r * a;
            a = a * a;
            k >>= 1;
        }
        cout << r.a[0][0] << '\n';
    }
}