Submission #106415

---

Source Code Expand

#include <iostream>
#include <vector>

using namespace std;

typedef long long LL;

const LL MOD = 1000000007;

void add(LL &var, LL val) {
    var = (var + val%MOD) % MOD;
}

int K;
vector<vector<LL>> fact;
vector<LL> dbl(const vector<LL> &v) {
    vector<LL> tmp(K*2, 0);
    for(int i = 0; i < K; ++i) {
        for(int j = 0; j < K; ++j) {
            add(tmp[i+j], v[i]*v[j]);
        }
    }
    for(int i = K; i < K*2; ++i) {
        for(int j = 0; j < K; ++j) {
            add(tmp[j], tmp[i]*fact[i][j]);
        }
    }
    tmp.resize(K);
    return tmp;
}

vector<LL> inc(const vector<LL> &v) {
    vector<LL> tmp(K+1, 0);
    for(int i = 0; i < K; ++i) {
        tmp[i+1] = v[i];
    }
    for(int j = 0; j < K; ++j) {
        add(tmp[j], tmp[K]*fact[K][j]);
    }
    tmp.resize(K);
    return tmp;
}

vector<LL> modpow(const vector<LL> &v, int N) {
    if(N == 1) return v;
    if(N == 2) return inc(v);
    vector<LL> tmp = dbl(modpow(v, N/2));
    if(N % 2 == 1) tmp = inc(tmp);
    return tmp;
}

int main() {
    int N;
    cin >> K >> N;

    fact.resize(K*2);
    // [0, K)
    for(int i = 0; i < K; ++i) {
        fact[i].resize(K, 0);
        fact[i][i] = 1;
    }
    // [K, K+1)
    fact[K].resize(K, 0);
    for(int i = 0; i < K; ++i) {
        fact[K][i] = 1;
    }
    // [K+1, 2K)
    for(int i = K+1; i < 2*K; ++i) {
        fact[i].resize(K, 0);
        for(int j = 0; j < K; ++j) {
            add(fact[i][j], fact[i-1][j]*2);
        }
        for(int j = 0; j < K; ++j) {
            fact[i][j] = (fact[i][j] - fact[i-K-1][j] + MOD) % MOD;
        }
    }

    vector<LL> vec(K, 0);
    vec[1] = 1;
    vec = modpow(vec, N-1);
    LL ans = 0;
    for(LL l : vec) {
        add(ans, l);
    }
    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result