Submission #74256174

---

Source Code Expand

#include <bits/stdc++.h>
#include <cassert>
#define print(vec) print_v(#vec, vec)
#define debug(x) cout << #x << ": " << x << endl
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;
ll qpow(ll x, ll k) {
    ll res = 1;
    while(k) {
        if(k & 1ll) res = res * x % mod;
        x = x * x % mod, k >>= 1;
    }
    return res;
}

template<typename T>
void print_v(string name, const vector<T>& vec) {
    cout << name << ": " << endl;
    for(auto v: vec) cout << v << ' ';
    cout << endl;
}

ll kitamasa(const vector<ll>& coef, const vector<ll>& a, ll n) {
    if(n < (int)a.size()) return a[n];

    int k = coef.size();
    assert(k != 0);

    auto compose = [&](const vector<ll>& A, const vector<ll>& _B) -> vector<ll> {
        // print(A);
        // print(_B);
        // debug(k);

        vector<ll> B = _B;
        vector<ll> C(k);
        for(auto v: A) {
            for(int j = 0; j < k; j++) (C[j] += v * B[j] % mod) %= mod;

            ll back = B.back();
            for(int j = k - 1; j >= 1; j--)
                B[j] = (B[j - 1] + back * coef[j] % mod) % mod;
            B[0] = back * coef[0] % mod;
        }

        // print(C);

        return C;
    };

    vector<ll> res_c(k), c(k);
    res_c[0] = 1, c[1] = 1;
    while(n) {
        if(n & 1ll) res_c = compose(res_c, c);
        n >>= 1, c = compose(c, c);
    }
    ll res = 0;
    for(int j = 0; j < k; j++) (res += res_c[j] * a[j] % mod) %= mod;
    return res;
}
void solve() {
    int k; ll n;
    cin >> k >> n;
    cout << kitamasa(vector(k, 1ll), vector(k, 1ll), n - 1) << endl;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    // freopen("A.in", "r", stdin);
    // freopen("A.out", "w", stdout);
    int T = 1;
    // cin >> T;
    while(T--) solve();
}

Submission Info

Judge Result