Typical DP Contest T - フィボナッチ

問題文

http://tdpc.contest.atcoder.jp/tasks/tdpc_fibonacci

解法

今なら，通称きたまさ法とよばれている方法でやります．
きたまさ法自体の説明は省略します．

アイデアとしては，一般項を最初の K 項の線形結合で表そう，というものです．

ソースコード

#include <bits/stdc++.h>
using namespace std;
 
constexpr int M = 1e9 + 7;
 
 
class kitamasa {
public:
    // d: coefficient
    kitamasa(std::vector<long long> const& d_, long long const m = 1e9+7)
        : k(d_.size()),
          d(d_),
          M(m)
    {}
 
    void inc(std::vector<long long>& v) {
        std::rotate(v.begin(), v.begin() + (k - 1), v.begin() + k);
        long long l = v[0];
        v[0] = 0;
        for(int i = 0; i < k; ++i) {
            (v[i] += d[i] * l) %= M;
        }
    }
    void dbl(std::vector<long long>& v) { 
        auto buf = v;
        std::vector<long long> res(k);
        for(int i = 0; i < k; ++i) {
            for(int j = 0; j < k; ++j) {
                (res[j] += buf[j] * v[i]) %= M;
            }
            inc(buf);
        }
        v = std::move(res);
    }
 
    // calc a_n
    long long calc(long long n) {
        std::vector<long long> res(k);
        res[0] = 1;
        int j = 63;
        while(!(n & (1 << j))) {
            --j;
        }
        for(int i = j + 1; i >= 0; --i) {
            dbl(res);
            if(n & (1LL << i)) {
                inc(res);
            }
        }
 
        long long ans = 0;
        for(int i = 0; i < k; ++i) {
            (ans += res[i] * d[i]) %= M;
        }
        return ans;
    }
 
private:
    int k;
    std::vector<long long> d;
    long long const M;
};
 
using ll = long long;
 
int main() {
    int K, N;
    cin >> K >> N;
    vector<ll> d(K, 1);
    kitamasa kit(d);
    cout << kit.calc(N - 1) << endl;
}

感想

（線形）代数にある程度理解があるなら，アイデアはすぐわかると思います．