FFTl裸题,小于的部分直接做,大于的部分倒序后再做就行了。
#include
using namespace std;
const int MAXN = 1 const double Pi = acos(-1.0);
struct cp {
double x, y;
cp() { x = y = 0; }
cp(double x, double y) : x(x), y(y) {}
inline cp operator+(const cp &o) const { return cp(x + o.x, y + o.y); }
inline cp operator-(const cp &o) const { return cp(x - o.x, y - o.y); }
inline cp operator*(const cp &o) const { return cp(x * o.x - y * o.y, x * o.y + o.x * y); }
} f[MAXN], g[MAXN], b[MAXN];
int rev[MAXN];
inline void DFT(cp *arr, int len, int flg) {
for (int i = 0; i if (i swap(arr[i], arr[rev[i]]);
for (int i = 2; i cp wn = cp(cos(2 * Pi / i), flg * sin(2 * Pi / i));
for (int j = 0; j cp w = cp(1, 0);
for (int k = j; k cp x = arr[k], y = arr[k + i / 2] * w;
arr[k] = x + y;
arr[k + i / 2] = x - y;
}
}
}
if (flg == -1)
for (int i = 0; i }
int n;
int main() {
scanf("%d", &n);
for (int i = 1; i int len = 1;
while (len for (int i = 0; i > 1] >> 1) | ((i & 1) * (len >> 1));
DFT(f, len, 1), DFT(g, len, 1), DFT(b, len, 1);
for (int i = 0; i DFT(f, len, -1), DFT(g, len, -1);
for (int i = 1; i }