| 397 | return V; |
| 398 | } |
| 399 | static void convolution(const vector<int>& a, const vector<int>& b, vector<int>& c) { |
| 400 | int sz = a.size() + b.size() - 1; |
| 401 | int n = 1 << int(ceil(log2(sz))); |
| 402 | vector<Cplx> av(n, 0), bv(n, 0), cv; |
| 403 | for (int i = 0; i < a.size(); i++) av[i] = a[i]; |
| 404 | for (int i = 0; i < b.size(); i++) bv[i] = b[i]; |
| 405 | cv = FFT(bv); |
| 406 | bv = FFT(av); |
| 407 | for (int i = 0; i < n; i++) av[i] = bv[i] * cv[i]; |
| 408 | cv = FFT(av, -1); |
| 409 | c.resize(n); |
| 410 | ll carry = 0; |
| 411 | for (int i = 0; i < n; i++) { |
| 412 | ll t = ll(cv[i].real() + 0.5) + carry; |
| 413 | carry = t / FBASE; |
| 414 | c[i] = t % FBASE; |
| 415 | } |
| 416 | } |
| 417 | BigInt mul_simple(const BigInt &v) const { |
| 418 | BigInt res; |
| 419 | res.sgn = sgn * v.sgn; |