| 9 | tmp[i-j-1] = (tmp[i-j-1] + tmp[i]*c[j]) % mod; |
| 10 | rep(i,0,a.size()) a[i] = i < c.size() ? tmp[i] : 0; } |
| 11 | ll nth_term(const vector<ll> &init, const vector<ll> &c, |
| 12 | ll n, ll mod) { |
| 13 | if (n < init.size()) return init[n]; |
| 14 | int l = max(2, (int)c.size()); |
| 15 | vector<ll> x(l), t(l); x[1]=t[0]=1; |
| 16 | while (n) { if (n & 1) mul(t, x, c, mod); |
| 17 | mul(x, x, c, mod); n >>= 1; } |
| 18 | ll res = 0; |
| 19 | rep(i,0,c.size()) res = (res + init[i] * t[i]) % mod; |
| 20 | return res; } |
| 21 | // vim: cc=60 ts=2 sts=2 sw=2: |