diff options
Diffstat (limited to 'content/math/linearRecurrence.cpp')
| -rw-r--r-- | content/math/linearRecurrence.cpp | 30 |
1 files changed, 30 insertions, 0 deletions
diff --git a/content/math/linearRecurrence.cpp b/content/math/linearRecurrence.cpp new file mode 100644 index 0000000..c15c25c --- /dev/null +++ b/content/math/linearRecurrence.cpp @@ -0,0 +1,30 @@ +// constexpr ll mod = 998244353; +// vector<ll> mul(const vector<ll> &a, const vector<ll> &b){ +// vector<ll> c(sz(a) + sz(b) - 1); +// for(int i = 0; i < sz(a); i++){ +// for(int j = 0; j < sz(b); j++){ +// c[i+j] += a[i]*b[j] % mod; +// } +// } +// for(ll &x : c) x %= mod; +// return c; +// } + +ll kthTerm(const vector<ll>& f, const vector<ll>& c, ll k){ + int n = sz(c); + vector<ll> q(n+1, 1); + for(int i = 1; i <= n; i++) q[i] = (mod-c[i-1])%mod; + vector<ll> p = mul(f, q); + p.resize(n); + p.push_back(0); + do{ + vector<ll> q2 = q; + for(int i = 1; i <= n; i += 2) q2[i] = (mod - q2[i]) % mod; + vector<ll> x = mul(p, q2), y = mul(q, q2); + for(int i = 0; i <= n; i++){ + p[i] = i == n ? 0 : x[2*i + (k&1)]; + q[i] = y[2*i]; + } + }while(k /= 2); + return p[0]; +}
\ No newline at end of file |