diff options
Diffstat (limited to 'content/math/linearRecurrence.cpp')
| -rw-r--r-- | content/math/linearRecurrence.cpp | 14 |
1 files changed, 7 insertions, 7 deletions
diff --git a/content/math/linearRecurrence.cpp b/content/math/linearRecurrence.cpp index c15c25c..ab86f71 100644 --- a/content/math/linearRecurrence.cpp +++ b/content/math/linearRecurrence.cpp @@ -10,21 +10,21 @@ // return c; // } -ll kthTerm(const vector<ll>& f, const vector<ll>& c, ll k){ +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> q(n + 1, 1); + 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); - do{ + do { vector<ll> q2 = q; - for(int i = 1; i <= n; i += 2) q2[i] = (mod - q2[i]) % mod; + 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++){ + 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); + } while (k /= 2); return p[0]; }
\ No newline at end of file |