TDPC T フィボナッチ kitamasa きたまさ

##問題
https://atcoder.jp/contests/tdpc/tasks/tdpc_fibonacci
##見た感じ
Nがでかい、kもでかい、繰り返し自乗法でも間に合わない。
どうすればいいんだあ。
kitamasa法という線形漸化式を高速に計算する手法があるそうです。
いろいろテクニックを詰め込むとk次の線形漸化式で定まる数列のn項目が$O(k\log k \log n)$で求まるみたいですが、まずは簡単な方（それでも大変よ）の$O(k^2 \log n)$で計算できる手法を実装すべし。
kitamasa法についてはこのサイトを参考にしました。詳しいことはこのサイトに書いてあります。
kitamasa法は数列$a_n$の$a_1 ,...,a_k$による展開式の係数を知って入れば、$a_{n+1}$の展開したときの係数も$O(k)$で求まるし、$a_{2*n}$の展開したときの係数も$O(k^2 )$で求まるから、
これらを使って繰り返し自乗法していく方法です。

kitamasa

struct kitamasa{
    ll n;//次数
    vector<mint> a;//漸化式の係数
    vector<vector<mint>> mem;//a_n+i = \sum a_j mem[i][n-1-j]
    //kitamasa(漸化式の係数,次数)
    kitamasa(vector<mint> c,ll N) : a(c),n(N){
        vector<mint> r(2*n,0);
        rep(i,n)r[i]=c[i];
        mem.push_back(r);
        rep(i,n+1){
            mem.push_back(oneplass(mem[i]));
        }
    }
    //畳み込み
    vector<mint> closs(vector<mint> b){
        vector<mint> res(2*n,0);  
        vrep(i,2*n-2+1){
            mint a=0;
            rep(j,i+1){
                a+=b[j]*b[i-j];
            }
            res[i]=a;
        }
        return res;
    }
    //a_l の係数-> a_l+1 の係数
    vector<mint> oneplass(vector<mint> b){
        vector<mint> res(2*n,0);
        rep(i,n-1){
            res[i]=b[i+1]+b[0]*a[i];
        }
        res[n-1]=b[0]*a[n-1];
        return res;
    }
    //a_l の係数-> a_2*l の係数
    vector<mint> twotimes(vector<mint> b){
        vector<mint> res(2*n,0);
        auto bb=closs(b);
        rep(i,n-1){
            rep(j,n){
                bb[2*n-2-j]+=bb[n-2-i]*mem[i][n-1-j];
            }
            bb[n-2-i]=0;
        }
        rep(i,n){
            res[n-1-i]=bb[2*n-2-i];
        }
        return res;
    }
    //calculate(n)=a_nの係数
    vector<mint> calculate(int m){
        vector<mint> res(2*n,0);
        if(m<n){
            res[m]=a[m];
            return res;
        }
        if(m<=2*n){
            return mem[m-n];
        }else{
            if(m%2==0){
                auto b=calculate(m/2);
                res=twotimes(b);
            }else{
                auto b=calculate((m-1)/2);
                res=twotimes(b);
                res=oneplass(res);
            }
        }
        return res;
    }
};

##解法
kitamasa法を実装して使用
##ソースコード

struct kitamasa{
    ll n;//次数
    vector<mint> a;//漸化式の係数
    vector<vector<mint>> mem;//a_n+i = \sum a_j mem[i][n-1-j]
    //kitamasa(漸化式の係数,次数)
    kitamasa(vector<mint> c,ll N) : a(c),n(N){
        vector<mint> r(2*n,0);
        rep(i,n)r[i]=c[i];
        mem.push_back(r);
        rep(i,n+1){
            mem.push_back(oneplass(mem[i]));
        }
    }
    //畳み込み
    vector<mint> closs(vector<mint> b){
        vector<mint> res(2*n,0);  
        vrep(i,2*n-2+1){
            mint a=0;
            rep(j,i+1){
                a+=b[j]*b[i-j];
            }
            res[i]=a;
        }
        return res;
    }
    //a_l の係数-> a_l+1 の係数
    vector<mint> oneplass(vector<mint> b){
        vector<mint> res(2*n,0);
        rep(i,n-1){
            res[i]=b[i+1]+b[0]*a[i];
        }
        res[n-1]=b[0]*a[n-1];
        return res;
    }
    //a_l の係数-> a_2*l の係数
    vector<mint> twotimes(vector<mint> b){
        vector<mint> res(2*n,0);
        auto bb=closs(b);
        rep(i,n-1){
            rep(j,n){
                bb[2*n-2-j]+=bb[n-2-i]*mem[i][n-1-j];
            }
            bb[n-2-i]=0;
        }
        rep(i,n){
            res[n-1-i]=bb[2*n-2-i];
        }
        return res;
    }
    //calculate(n)=a_nの係数
    vector<mint> calculate(int m){
        vector<mint> res(2*n,0);
        if(m<n){
            res[m]=a[m];
            return res;
        }
        if(m<=2*n){
            return mem[m-n];
        }else{
            if(m%2==0){
                auto b=calculate(m/2);
                res=twotimes(b);
            }else{
                auto b=calculate((m-1)/2);
                res=twotimes(b);
                res=oneplass(res);
            }
        }
        return res;
    }
};
const int N_MAX=0;
ll n,k,a[1002];

int main(){
    int x,y;
    //入力
    cin>>k>>n;
    //処理
    vector<mint> b(k,1);
    kitamasa kita(b,k);
    
    auto res=kita.calculate(n-1);
    mint ans=0;
    rep(i,k){
        ans+=res[i];
    }
    //出力
    cout << ans <<endl;
}