From a898bac55c6cd7c51fef5e6735aa3a316a18da7b Mon Sep 17 00:00:00 2001 From: mzuenni Date: Wed, 11 Sep 2024 10:39:00 +0200 Subject: change tests --- content/math/linearRecurrence.cpp | 26 +++++++++++++------------- 1 file changed, 13 insertions(+), 13 deletions(-) (limited to 'content') 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 mul(const vector &a, const vector &b){ -// vector 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 mul(const vector& a, const vector& b) { + vector 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& f, const vector& c, ll k) { int n = sz(c); vector 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 p = mul(f, q); p.resize(n); p.push_back(0); @@ -27,4 +27,4 @@ ll kthTerm(const vector& f, const vector& c, ll k) { } } while (k /= 2); return p[0]; -} \ No newline at end of file +} -- cgit v1.2.3