Bostan-Mori Algorithm
(FPS/nthterm.hpp)

• View this file on GitHub
• Last update: 2022-02-02 03:30:36+09:00
• Include: #include "FPS/nthterm.hpp"

Verified with

• Verify/LC_kth_term_of_linearly_recurrent_sequence.test.cpp

Code

#pragma once

template<typename T>T nth(Poly<T> p,Poly<T> q,ll n){
    while(n){
        Poly<T> base(q),np,nq;
        for(int i=1;i<(int)q.size();i+=2)base[i]=-base[i];
        p*=base; q*=base;
        for(int i=n&1;i<(int)p.size();i+=2)np.emplace_back(p[i]);
        for(int i=0;i<(int)q.size();i+=2)nq.emplace_back(q[i]);
        swap(p,np); swap(q,nq);
        n>>=1;
    }
    return p[0]/q[0];
}

/**
 * @brief Bostan-Mori Algorithm
 */

#line 2 "FPS/nthterm.hpp"

template<typename T>T nth(Poly<T> p,Poly<T> q,ll n){
    while(n){
        Poly<T> base(q),np,nq;
        for(int i=1;i<(int)q.size();i+=2)base[i]=-base[i];
        p*=base; q*=base;
        for(int i=n&1;i<(int)p.size();i+=2)np.emplace_back(p[i]);
        for(int i=0;i<(int)q.size();i+=2)nq.emplace_back(q[i]);
        swap(p,np); swap(q,nq);
        n>>=1;
    }
    return p[0]/q[0];
}

/**
 * @brief Bostan-Mori Algorithm
 */

Back to top page