text: q Output 0000100 0001001 0000000 0000000 0000000 Input 10 10 fwtoayylhw yyaryyjawr ywrdzwhscy hnsyyxiphn bnjwzyyjvo kkjgseenwn gvmiflpcsy lxvkwrobwu wyybbcocyy yysijsvqry 2 2 ??yy Output 1000100000 0000000001 0001000000 0000010000 0000000000 0000000000 0000000000 0100000010 1000000001 0000010000 Input 8 6 ibrgxl xqdcsg okbcgi tvpetc xgxxig igghzo lmlaza gpswzv 1 4 gx??Output 000100 000001 000000 000000 010001 000000 000000 000000 # Solution #include <bits/stdc++.h> using namespace std; static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL; template <typename T, typename U> static void amin(T &x, U y) { if (y < x) x = y; } template <typename T, typename U> static void amax(T &x, U y) { if (x < y) x = y; } struct FFTCoeffTable { static const int logn = 10, n = 1 << logn; complex<double> coeffs[n]; FFTCoeffTable() { const double PI = 3.141592653589793238462643383279L; for (int i = 0; i < n; ++i) { double theta = 2 * PI * i / n; coeffs[i] = complex<double>(cos(theta), sin(theta)); } } } fftCoeffTable; void fft_core(complex<double> *x, int logn, int sign) { int n = 1 << logn; for (int i = 1, j = 0; i < n; ++i) { int h = n >> 1; while (((j ^= h) & h) == 0) h >>= 1; if (i < j) swap(x[i], x[j]); } for (int logm = 1; logm <= logn; ++logm) { int winc = (1 << (fftCoeffTable.logn - logm)) * sign; if (winc < 0) winc += fftCoeffTable.n; int h = 1 << (logm - 1); for (int i = 0; i < n; i += 1 << logm) { int wk = 0; for (int j = i; j < i + h; ++j) { const complex<double> &w = fftCoeffTable.coeffs[wk]; int k = j + h; double lr = x[k].real() * w.real() - x[k].imag() * w.imag(); double li = x[k].real() * w.imag() + x[k].imag() * w.real(); x[k] = complex<double>(x[j].real() - lr, x[j].imag() - li); x[j] = complex<double>(x[j].real() + lr, x[j].imag() + li); if ((wk += winc) >= fftCoeffTable.n) wk -= fftCoeffTable.