FFT学习笔记

这里先占个坑，等下午再来补坑

代码

$\text{FFT}$

#include<cstdio>
#include<cctype>
#include<algorithm>
#include<complex>
#define RG register

inline int read()
{
	int data = 0, w = 1; char ch = getchar();
	while(ch != ‘-‘ && (!isdigit(ch))) ch = getchar();
	if(ch == ‘-‘) w = -1, ch = getchar();
	while(isdigit(ch)) data = data * 10 + (ch ^ 48), ch = getchar();
	return data * w;
}

const int maxn(3e6 + 10);
const double pi(acos(-1));
typedef std::complex<double> complex;

int n, m, r[maxn], P;
complex a[maxn], b[maxn];

template<int opt> void FFT(complex *p)
{
	for(RG int i = 0; i < n; i++) if(i < r[i]) std::swap(p[i], p[r[i]]);
	for(RG int i = 1; i < n; i <<= 1)
	{
		complex rot(cos(pi / i), opt * sin(pi / i));
		for(RG int j = 0; j < n; j += (i << 1))
		{
			complex w(1, 0);
			for(RG int k = 0; k < i; ++k, w *= rot)
			{
				complex x = p[j + k], y = w * p[i + j + k];
				p[j + k] = x + y, p[i + j + k] = x - y;
			}
		}
	}
}

int main()
{
	n = read(), m = read();
	for(RG int i = 0; i <= n; i++) a[i] = read();
	for(RG int i = 0; i <= m; i++) b[i] = read();
	for(m += n, n = 1; n <= m; n <<= 1, ++P);
	for(RG int i = 0; i < n; i++)
		r[i] = (r[i >> 1] >> 1) | ((i & 1) << (P - 1));
	FFT<1>(a), FFT<1>(b);
	for(RG int i = 0; i < n; i++) a[i] *= b[i];
	FFT<-1>(a);
	for(RG int i = 0; i <= m; i++) printf("%d ", (int)(a[i].real() / n + .5));
	return 0;
}

$\text{NTT}$

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define RG register
#define file(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout);
#define clear(x, y) memset(x, y, sizeof(x))

inline int read()
{
	int data = 0, w = 1; char ch = getchar();
	while(ch != ‘-‘ && (!isdigit(ch))) ch = getchar();
	if(ch == ‘-‘) w = -1, ch = getchar();
	while(isdigit(ch)) data = data * 10 + (ch ^ 48), ch = getchar();
	return data * w;
}

const int maxn(3e6 + 10), g(3), Mod(998244353), phi(Mod - 1);
inline int fastpow(int x, int y)
{
	int ans = 1;
	while(y)
	{
		if(y & 1) ans = 1ll * ans * x % Mod;
		x = 1ll * x * x % Mod, y >>= 1;
	}
	return ans;
}

int n, m, r[maxn], P, a[maxn], b[maxn];
template<int opt> void FFT(int *p)
{
	for(RG int i = 0; i < n; i++) if(i < r[i]) std::swap(p[i], p[r[i]]);
	for(RG int i = 1; i < n; i <<= 1)
	{
		int rot = fastpow(g, phi / (i << 1));
		for(RG int j = 0; j < n; j += (i << 1))
		{
			int w = 1;
			for(RG int k = 0; k < i; ++k, w = 1ll * w * rot % Mod)
			{
				int x = p[j + k], y = 1ll * w * p[i + j + k] % Mod;
				p[j + k] = (x + y) % Mod, p[i + j + k] = (x - y + Mod) % Mod;
			}
		}
	}
	if(opt == -1) std::reverse(p + 1, p + n);
}

int main()
{
#ifndef ONLINE_JUDGE
	file(cpp);
#endif
	n = read(), m = read();
	for(RG int i = 0; i <= n; i++) a[i] = read();
	for(RG int i = 0; i <= m; i++) b[i] = read();
	for(m += n, n = 1; n <= m; n <<= 1, ++P);
	for(RG int i = 0; i < n; i++)
		r[i] = (r[i >> 1] >> 1) | ((i & 1) << (P - 1));
	FFT<1>(a), FFT<1>(b);
	for(RG int i = 0; i < n; i++) a[i] = 1ll * a[i] * b[i] % Mod;
	FFT<-1>(a);
	int inv = fastpow(n, Mod - 2);
	for(RG int i = 0; i <= m; i++) printf("%lld ", 1ll * a[i] * inv % Mod);
	return 0;
}

FFT学习笔记

原文：https://www.cnblogs.com/cj-xxz/p/10173161.html