| 1 | ll tmp[10000]; |
| 2 | void mul(vector<ll> &a, vector<ll> &b, |
| 3 | const vector<ll> &c, ll mod) { |
| 4 | memset(tmp,0,sizeof(tmp)); |
| 5 | rep(i,0,a.size()) rep(j,0,b.size()) |
| 6 | tmp[i+j] = (tmp[i+j] + a[i] * b[j]) % mod; |
| 7 | for (int i=(int)(a.size()+b.size())-2; i>=c.size(); i--) |
| 8 | rep(j,0,c.size()) |
| 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]; |