This documentation is automatically generated by online-judge-tools/verification-helper
#include "math/fps/kth-term-of-linearly-recurrent-sequence.hpp"
線形線形漸化的数列の第 $N$ 項を求める。
$k$ 項間漸化式 $a_n = \sum_{d=1}^{k} c_d a_{n-d} (n \ge d)$ が存在するとき数列 $a$ は線形漸化的数列であるという。線形漸化的数列 $a$ は、初項 $(a_1, \cdots, a_{d-1})$ と係数 $c = (c_1, \cdots, c_d), c_d \neq 0$ を用いることで定義される。$d$ を位数と呼ぶ。
位数 $d$ の線形漸化式が存在するとき、ある次数 $d$ の $Q(0)=1$ 満たす多項式 $Q(x)$ と次数 $d-1$ 以下の多項式 $P(x)$ が存在して、$G(x)=\frac {P(x)} {Q(x)}$ が母関数となる。具体的には、
$Q(x) = 1 - c_1x - c_2x^2 - \cdots - c_kx^k$
$P(x) = Q(x)(a_0 + a_1x + a_2x^2 + \cdots + a^{k-1}x^{k-1}) \pmod {x^k}$
とすればよい。$P(x)$ は $Q(x)$ と $a$ を畳み込むと求められる。
従って、数列 $a$ の第 $N$ 項を求めるために、 $\frac {P(x)} {Q(x)}$ の $x^N$ の係数を求めればよくて、Bostan-Mori Algorithm を用いることで効率的に計算できる。
$O(K \log K \log N)$
#include "coeff-of-rational-function.hpp"
/**
* @brief Kth Term of Linearly Recurrent Sequence
*
*/
template< template< typename > class FPS, typename Mint >
Mint kth_term_of_linearly_recurrent_sequence(const FPS< Mint > &a, FPS< Mint > c, int64_t k) {
assert(a.size() == c.size());
c = FPS< Mint >{1} - (c << 1);
return coeff_of_rational_function((a * c).pre(a.size()), c, k);
}
#line 1 "math/fps/coeff-of-rational-function.hpp"
/**
* @brief Coeff of Rational Function
*
*/
template< template< typename > class FPS, typename Mint >
Mint coeff_of_rational_function(FPS< Mint > P, FPS< Mint > Q, int64_t k) {
// compute the coefficient [x^k] P/Q of rational power series
Mint ret = 0;
if(P.size() >= Q.size()) {
auto R = P / Q;
P -= R * Q;
P.shrink();
if(k < (int) R.size()) ret += R[k];
}
if(P.empty()) return ret;
P.resize((int) Q.size() - 1);
auto sub = [&](const FPS< Mint > &as, bool odd) {
FPS< Mint > bs((as.size() + !odd) / 2);
for(int i = odd; i < (int) as.size(); i += 2) bs[i >> 1] = as[i];
return bs;
};
while(k > 0) {
auto Q2(Q);
for(int i = 1; i < (int) Q2.size(); i += 2) Q2[i] = -Q2[i];
P = sub(P * Q2, k & 1);
Q = sub(Q * Q2, 0);
k >>= 1;
}
return ret + P[0];
}
#line 2 "math/fps/kth-term-of-linearly-recurrent-sequence.hpp"
/**
* @brief Kth Term of Linearly Recurrent Sequence
*
*/
template< template< typename > class FPS, typename Mint >
Mint kth_term_of_linearly_recurrent_sequence(const FPS< Mint > &a, FPS< Mint > c, int64_t k) {
assert(a.size() == c.size());
c = FPS< Mint >{1} - (c << 1);
return coeff_of_rational_function((a * c).pre(a.size()), c, k);
}