Zerojudge f996：N項的費氏數列 - Extreme

Zerojudge f996：N項的費氏數列 - Extreme

題目大意：$a[1] \sim a[n] = 1, a[i] = sum (a[i - n] \sim a[i - 1])$, 求 $a[k] % (10^9 + 7)$。

解法：這篇有，只是我那時候還是國中，用了一個很慢的作法。其實可以先把矩陣先預處理好，快速冪的時候用 $\text{vector}$ 取代 $\text{matrix}$，總時間 $O(n^4\times\log(C) + t\times n^2\times\log(C))$。

$\text{Code：}$

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

#define Waimai ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

const int MOD = 1e9 + 7;

struct Mat {
    vector<vector<int>> a;
    int n;
    Mat() {}
    Mat (int n, bool b) : n (n) {
        a.resize (n + 1, vector<int> (n + 1));
        if (b) {
            FOR (i, 1, n) a[1][i] = 1;
            FOR (i, 2, n) FOR (j, 1, n) a[i][j] = i - 1 == j;
        } else {
            FOR (i, 1, n) FOR (j, 1, n) a[i][j] = i == j;
        }
    }
    Mat operator * (const Mat &m) const {
        Mat re = *this;
        FOR (i, 1, n) FOR (j, 1, n) {
            long long sum = 0;
            FOR (k, 1, n) {
                sum += 1ll * a[i][k] * m.a[k][j];
                sum %= MOD;
            }
            re.a[i][j] = sum;
        }
        return re;
    }
    vector<int> operator * (const vector<int> &v) const {
        vector<int> re (n + 1);
        FOR (i, 1, n) {
            long long sum = 0;
            FOR (k, 1, n) {
                sum += 1ll * a[i][k] * v[k];
                sum %= MOD;
            }
            re[i] = sum;
        }
        return re;
    }
};

Mat mat[16][61];

void init() {
    FOR (i, 2, 15) {
        mat[i][0] = Mat (i, 1);
        FOR (j, 1, 60) mat[i][j] = mat[i][j - 1] * mat[i][j - 1];
    }
}

void solve () {
    int n;
    long long k;
    cin >> n >> k;
    if (k <= n) {
        cout << "1\n";
        return;
    }
    vector<int> ans (n + 1, 1);
    k--;
    for (int i = 0; k; i++, k >>= 1) {
        if (k & 1) {
            ans = mat[n][i] * ans;
        }
    }
    cout << ans[n] << '\n';
}

int main() {
    Waimai;
    init();
    int tt;
    cin >> tt;
    while (tt--) {
        solve();
    }
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！