Submission #19372238

---

Source Code Expand

#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

Judge Result