Submission #19372238


Source Code Expand

Copy
#include <bits/stdc++.h>
#include <atcoder/modint>
using namespace std;
using namespace atcoder;
using mint = modint1000000007;

__attribute__((constructor))
void fast_io() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

// O(k^2 log(n))
template<typename T>
struct kitamasa {
    // a[n] = d[0] * a[n - k] + d[1] * a[n - k + 1] + ...... + d[k - 1] * a[n - 1]
    vector<T> a;
    vector<T> d;
    int k;
    kitamasa(const vector<T>& a, const vector<T>& d) : a(a), d(d), k((int)a.size()) {}

    vector<T> rec(long long n) {
        assert(k <= n);
        if (n == k) return d;
        vector<T> res(k);
        if (n % 2 == 1 || n / 2 < k) {
            vector<T> x = rec(n - 1);
            for (int i = 0; i < k; ++i) res[i] = d[i] * x[k - 1];
            for (int i = 1; i < k; ++i) res[i] += x[i - 1];
        } else {
            vector x(k, vector<T>(k));
            x[0] = rec(n / 2);
            for (int i = 1; i < k; ++i) {
                for (int j = 0; j < k; ++j) x[i][j] = d[i] * x[i - 1][k - 1];
                for (int j = 1; j < k; ++j) x[i][j] += x[i - 1][j - 1];
            }
            for (int i = 0; i < k; ++i) {
                for (int j = 0; j < k; ++j) {
                    res[i] += x[0][j] * x[j][i];
                }
            }
        }
        return res;
    }

    T calc(long long n) {
        assert(0 <= n);
        if (n < k) return a[n];
        vector<T> x = rec(n);
        T res = 0;
        for (int i = 0; i < k; ++i) res += x[i] * a[i];
        return res;
    }
};

int main() {
    int k, n;
    cin >> k >> n;
    n--;
    vector<mint> a(k, 1), d(k, 1);
    kitamasa solver(a, d);
    cout << solver.calc(n).val() << '\n';
}

Submission Info

Submission Time
Task T - フィボナッチ
User Lorent
Language C++ (GCC 9.2.1)
Score 8
Code Size 1759 Byte
Status AC
Exec Time 187 ms
Memory 81972 KB

Judge Result

Set Name All
Score / Max Score 8 / 8
Status
AC × 7
Set Name Test Cases
All 00, 01, 02, 03, 04, 90, 91
Case Name Status Exec Time Memory
00 AC 187 ms 81972 KB
01 AC 99 ms 45624 KB
02 AC 186 ms 81876 KB
03 AC 39 ms 16540 KB
04 AC 5 ms 3552 KB
90 AC 2 ms 3612 KB
91 AC 3 ms 3472 KB