bostan_mori
(src/fps/bostan_mori.hpp)

• View this file on GitHub
• Last update: 2024-11-09 01:34:39+09:00
• Include: #include "src/fps/bostan_mori.hpp"

bostan_mori

mint bostan_mori(FPS<mint> a, FPS<mint> c, ll k)

斉次線形漸化式

\[a_i = \sum\limits_{j = 0}^{d - 1} c_j a_{i - 1 - j}\]

の $a$ の前 $n ~(\geq d)$ 項と $c$ が与えられたときに $a_k$ を返します．

制約

• $0 \leq k$
• $d \leq n$

計算量

• $O(d \log d \log k)$

Depends on

• template (src/template/template.hpp)

Required by

• nth_term (src/fps/nth_term.hpp)

Verified with

• verify/library_checker/other/kth_term_of_linearly_recurrent_sequence.test.cpp
• verify/yukicoder/1559.test.cpp

Code

#pragma once
#include "../template/template.hpp"
template <template <typename> typename FPS, typename mint>
mint bostan_mori(const FPS<mint>& a, const FPS<mint>& c, long long k) {
    assert(k >= 0);
    if(k < (int)a.size()) return a[k];
    assert(a.size() >= c.size());
    FPS<mint> q = FPS<mint>{1} - (c << 1);
    FPS<mint> p = (a * q).pre((int)c.size());
    if(p.empty()) return 0;
    while(k > 0) {
        auto q2 = q;
        for(int i = 1; i < (int)q2.size(); i += 2) q2[i] = -q2[i];
        const auto s = p * q2;
        const auto t = q * q2;
        if(k & 1) {
            for(int i = 1; i < (int)s.size(); i += 2) p[i >> 1] = s[i];
            for(int i = 0; i < (int)t.size(); i += 2) q[i >> 1] = t[i];
        } else {
            for(int i = 0; i < (int)s.size(); i += 2) p[i >> 1] = s[i];
            for(int i = 0; i < (int)t.size(); i += 2) q[i >> 1] = t[i];
        }
        k >>= 1;
    }
    return p[0];
}

#line 2 "src/template/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
    SetupIO() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout << fixed << setprecision(30);
    }
} setup_io;
#line 3 "src/fps/bostan_mori.hpp"
template <template <typename> typename FPS, typename mint>
mint bostan_mori(const FPS<mint>& a, const FPS<mint>& c, long long k) {
    assert(k >= 0);
    if(k < (int)a.size()) return a[k];
    assert(a.size() >= c.size());
    FPS<mint> q = FPS<mint>{1} - (c << 1);
    FPS<mint> p = (a * q).pre((int)c.size());
    if(p.empty()) return 0;
    while(k > 0) {
        auto q2 = q;
        for(int i = 1; i < (int)q2.size(); i += 2) q2[i] = -q2[i];
        const auto s = p * q2;
        const auto t = q * q2;
        if(k & 1) {
            for(int i = 1; i < (int)s.size(); i += 2) p[i >> 1] = s[i];
            for(int i = 0; i < (int)t.size(); i += 2) q[i >> 1] = t[i];
        } else {
            for(int i = 0; i < (int)s.size(); i += 2) p[i >> 1] = s[i];
            for(int i = 0; i < (int)t.size(); i += 2) q[i >> 1] = t[i];
        }
        k >>= 1;
    }
    return p[0];
}

Back to top page