blob: 1fd9f5c45b04e71825ccff38a2cafa8f6e4b47b7 (
plain)
1
2
3
4
5
6
7
8
|
void fft(vector<ll>& a, bool inv = false) {
int n = sz(a);
for (int s = 1; s < n; s *= 2) {
for (int i = 0; i < n; i += 2 * s) {
for (int j = i; j < i + s; j++) {
ll& u = a[j], &v = a[j + s];
tie(u, v) = inv ? pair(v - u, u) : pair(v, u + v);
}}}}
|
