| 336 | return ret.mod_xk(n) * s; |
| 337 | } |
| 338 | poly root(int n, int k = 2) const { //kth root of p(x) mod x^n |
| 339 | if(is_zero()) return *this; |
| 340 | if (k == 1) return mod_xk(n); |
| 341 | assert(a[0] == 1); |
| 342 | poly q({1}); |
| 343 | for(int i = 1; i < n; i <<= 1){ |
| 344 | if(k == 2) q += mod_xk(2 * i) * q.inverse(2 * i); |
| 345 | else q = q * mint(k - 1) + mod_xk(2 * i) * q.inverse(2 * i).pow(k - 1, 2 * i); |
| 346 | q = q.mod_xk(2 * i) / mint(k); |
| 347 | } |
| 348 | return q.mod_xk(n); |
| 349 | } |
| 350 | poly mulx(mint x) { //component-wise multiplication with x^k |
| 351 | mint cur = 1; poly ans(*this); |
| 352 | for(int i = 0; i < size(); i++) ans.a[i] *= cur, cur *= x; |