| 301 | } |
| 302 | |
| 303 | static vector<int> convert_base(const vector<int> &a, int old_digits, int new_digits) { |
| 304 | vector<ll> p(max(old_digits, new_digits) + 1); |
| 305 | p[0] = 1; |
| 306 | for (int i = 1; i < (int) p.size(); i++) |
| 307 | p[i] = p[i - 1] * 10; |
| 308 | vector<int> res; |
| 309 | ll cur = 0; |
| 310 | int cur_digits = 0; |
| 311 | for (int i = 0; i < (int) a.size(); i++) { |
| 312 | cur += a[i] * p[cur_digits]; |
| 313 | cur_digits += old_digits; |
| 314 | while (cur_digits >= new_digits) { |
| 315 | res.push_back((ll)(cur % p[new_digits])); |
| 316 | cur /= p[new_digits]; |
| 317 | cur_digits -= new_digits; |
| 318 | } |
| 319 | } |
| 320 | res.push_back((int) cur); |
| 321 | while (!res.empty() && !res.back()) |
| 322 | res.pop_back(); |
| 323 | return res; |
| 324 | } |
| 325 | |
| 326 | void fft(vector<Cplx>& a, bool invert) const { |
| 327 | int n = a.size(); |