p(g(x)) O(nlogn * sqrt(nlogn))
| 427 | // p(g(x)) |
| 428 | // O(nlogn * sqrt(nlogn)) |
| 429 | poly composition(poly g, int deg) { |
| 430 | int n = size(); |
| 431 | int k = 1; |
| 432 | while (k * k <= n) k++; |
| 433 | k--; |
| 434 | int d = n / k; |
| 435 | if (k * d < n) d++; |
| 436 | vector<poly> pw(k + 3, poly({1})); |
| 437 | for(int i = 1; i <= k + 2; i++) { |
| 438 | pw[i] = pw[i - 1] * g; |
| 439 | if (pw[i].size() > deg) pw[i].a.resize(deg); |
| 440 | } |
| 441 | vector<poly> fi(k, poly(deg, 0)); |
| 442 | for (int i = 0; i < k; i++) { |
| 443 | for (int j = 0; j < d; j++) { |
| 444 | int idx = i * d + j; |
| 445 | if (idx >= n) break; |
| 446 | int sz = min(fi[i].size(), pw[j].size()); |
| 447 | for (int t = 0; t < sz; t++) { |
| 448 | fi[i].a[t] += pw[j][t] * coef(idx); |
| 449 | } |
| 450 | } |
| 451 | } |
| 452 | poly ret(deg, 0), gd({1}); |
| 453 | for (int i = 0; i < k; i++){ |
| 454 | fi[i] = fi[i] * gd; |
| 455 | int sz = min((int)ret.size(), (int)fi[i].size()); |
| 456 | for (int j = 0; j < sz; j++) ret.a[j] += fi[i][j]; |
| 457 | gd = gd * pw[d]; |
| 458 | if (gd.size() > deg) gd.a.resize(deg); |
| 459 | } |
| 460 | return ret; |
| 461 | } |
| 462 | poly build(vector<poly> &ans, int v, int l, int r, vector<mint> &vec) { //builds evaluation tree for (x-a1)(x-a2)...(x-an) |
| 463 | if(l == r) return ans[v] = poly({-vec[l], 1}); |
| 464 | int mid = l + r >> 1; |