diff options
Diffstat (limited to 'content/math/linearRecurrence.cpp')
| -rw-r--r-- | content/math/linearRecurrence.cpp | 26 |
1 files changed, 13 insertions, 13 deletions
diff --git a/content/math/linearRecurrence.cpp b/content/math/linearRecurrence.cpp index ab86f71..a8adacd 100644 --- a/content/math/linearRecurrence.cpp +++ b/content/math/linearRecurrence.cpp @@ -1,19 +1,19 @@ -// 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; -// } +constexpr ll mod = 998244353; +// oder ntt mul @\sourceref{math/transforms/ntt.cpp}@ +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 = 0; i < n; i++) q[i + 1] = (mod - c[i])%mod; + for (int i = 0; i < n; i++) q[i + 1] = (mod - c[i]) % mod; vector<ll> p = mul(f, q); p.resize(n); p.push_back(0); @@ -27,4 +27,4 @@ ll kthTerm(const vector<ll>& f, const vector<ll>& c, ll k) { } } while (k /= 2); return p[0]; -}
\ No newline at end of file +} |